\documentclass[color=black, cn, math=newtx, 10pt, chinesefont=founder]{elegantbook}
\title{算法 \& Leetcode刷题之旅}
\subtitle{老码农的碎碎念}
\author{石头}
\date{\today}
\version{0.1}
\extrainfo{时间是不会浪费的，只要你认真的投入。--石头}
\setcounter{tocdepth}{3}

\cover{cover.jpg}
\usepackage{array}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}

\definecolor{customcolor}{RGB}{32,178,170}
\colorlet{coverlinecolor}{customcolor}
\usepackage{tabularx}

% 代码片段的样式
\usepackage{ctex}

\usepackage{listings}
\lstset{
    language=python,
    numbers=left,
    keywordstyle=\color{blue!70},
    commentstyle=\color{red!50!green!50!blue!50},
    frame=shadowbox,
    rulesepcolor=\color{ red!20!green!20!blue!20}
}
% ----------------

\begin{document}
\maketitle
\frontmatter

\chapter*{前言}
\markboth{Introduction}{前言}

​在哔哩哔哩上闲逛的时候，偶然点进一个讲刷LeetCode的视频，心想没事的时候自己也去刷刷题。

主要目的是：1) 防止长时间不写代码了，保持一定的代码能力；2) 工作中常用Java和C/C++，很少用到Python去写过真正的东西，借着刷题的机会再学习一下Python。

% 空行
​“不刷不知道，一刷吓一跳”，基本的数据结构已经还给学校了，一动手发现手很生。所谓“技不离手，曲不离口”，吃程序员这碗饭，代码能力还是不能丢，赶紧练起来。

​我的计划是：只要有时间，就去LeetCode上刷几道题，不分难度，使用Python来刷；将刷题中碰到的数据结构、算法、Python编程的知识都记录下来。对于难度为困难级别的题，以及看题解才做出来的题，要记录详细的分析过程。

2021年8月6日，感觉这种按照顺序刷题的方式效率不高，决定按照分类的方式来刷题。有时间就会去LeetCode上打卡，做周赛题。

​刷题的语言是Python（Python3.9版本），刷题使用的IDE环境是Pycharm Community版。
​相关的代码都保存在https://gitee.com/chysun2000/leetcode-study。

本文档使用\LaTeX{}和模板是\href{https://elegantlatex.org/}{ElegantBook}完成。

\vskip 1.5cm

\begin{flushright}
石头 \\
北京 2021-05-23
\end{flushright}


\tableofcontents

\mainmatter
\hypersetup{pageanchor=true}

\chapter{用到的Python编程技巧}
\section{常用代码片段}
\subsection{数组的定义方法}
\subsubsection{二维数组}

\begin{lstlisting}[language=python]
# matrix 为[m, n]的二维数组，子元素初始值为value
matrix = [[value] * n for _ in range(m)]
\end{lstlisting}

\subsubsection{三维数组}
\begin{lstlisting}[language=python]
# matrix=[m][n][k]的三维数组，子元素的初始值为value
matrix = [[[value] * for _a in range(k)] for _b in range(n)] for _c in range(m)]
\end{lstlisting}

\subsection{灵活使用List}
\subsubsection{用List实现栈的基本功能}
\begin{lstlisting}[language=python]
class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.data.pop()

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def top(self):
        if self.is_empty():
            return None
        else:
            return self.data[-1]
\end{lstlisting}

\subsubsection{复制List}
\begin{lstlisting}[language=python]
# 一维
new_list = list.copy()
# 二维
new_list = [list[i] for i in range(len(list))]
\end{lstlisting}

\subsubsection{将多个等长数组合并为一个List}
将下面的数组合并为一个$[('a1','b1','c1')...]$的数组
\begin{itemize}
    \item $arr1=['a1', 'a2', 'a3']$
    \item $arr2=['b1', 'b2', 'b3']$
    \item $arr3=['c1', 'c2', 'c3']$
\end{itemize}

\begin{lstlisting}[language=python]
arr1 = ['a1', 'a2', 'a3']
arr2 = ['b1', 'b2', 'b3']
arr3 = ['c1', 'c2', 'c3']

new_list = list(zip(arr1, arr2, arr3))
print(new_list)
\end{lstlisting}

结果如下：
\begin{lstlisting}
[('a1', 'b1', 'c1'), ('a2', 'b2', 'c2'), ('a3', 'b3', 'c3')]
\end{lstlisting}

\subsection{内置函数set()}
set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
\subsection{字典dict的使用}
\subsubsection{字典dict的遍历操作}
\begin{lstlisting}[language=python]
a = {'a':1, 'b':2, 'c':3, 'd':4}

# 遍历key
for key in a:
  	print(key)

for key in a.keys():
    print(key)

# 遍历value
for value in a.values():
    print(value)

# 遍历key和value
for key, value in a.items():
  	print(key + ':' + str(value))
\end{lstlisting}

\subsubsection{defaultdict的使用}
在使用dict的过程中常常会碰到KeyError的问题，collections的defaultdict就是用来解决这个问题的。当访问不存在的key时，defaultdict会返回默认的值。
\begin{itemize}
    \item int, 默认值是0
    \item str，默认值是“”
    \item list，默认值是[]
\end{itemize}

\begin{lstlisting}[language=python]
# value是整形的dict
int_dict = defaultdict(int)
# value是字符串的dict
str_dict = defaultdict(str)
# value是list的dict
list_dict = defaultdict(list)
\end{lstlisting}

\subsection{List的取值 Slice of a List}
\subsubsection{取奇数/偶数项}
Slice的语法如下：$list[start:stop:step]$

\begin{lstlisting}[language=python]
# 获取奇数项
def get_odd(list: List[int]) -> List[int]:
    return [list[i] for i in range(len(List)) if i % 2 == 1]

def get_odd(list: List[int]) -> List[int]:
    return list[1::2]

# 获取偶数项
def get_even(list: List[int]) -> List[int]:
    return [list[i] for i in range(len(List)) if i % 2 == 0]

def get_event(list: List[int]) -> List[int]:
    return list[::2]

\end{lstlisting}

\section{常用API}
\begin{table}[!htbp]
\centering
\caption{常用API}
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    API      & 说明                 \\
\midrule
    ord(ch)  & 返回字符ch对应的整数值  \\
    chr(value)  & 将value转换成对应的ASCII码  \\
    \%       &  取余数  \\
    //       &  求商  \\
    sorted(iterable, key=None, reverse=False) & 内置排序函数
    \newline 参数：
    \newline iterable：可迭代对象
    \newline key：主要是用来进行比较的元素
    \newline reverse：排序规则，True为降序，False为升序（默认值）
    \newline 返回值：排序后的列表 \\
    bin & 将整数转换为二进制数的字符串，bin(5) => ‘0b101’ \\
\bottomrule
\end{tabularx}
\end{table}

\chapter{基本算法和数据结构}
\section{二分查找法}
\subsection{代码框架}

\begin{lstlisting}[language=python]
def binary_search(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]

        if target == mid_value:
            return mid
        elif target < mid_value:
            right = mid - 1
        else:
            left = mid + 1

    return -1

def binary_search_left(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]

        if target == mid_value:
            right = mid - 1
        elif target < mid_value:
            right = mid - 1
        else:
            left = mid + 1

    return left - 1

def binary_search_right(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]

        if target == mid_value:
            left = mid + 1
        elif target < mid_value:
            right = mid - 1
        else:
            left = mid + 1

    return left
\end{lstlisting}

\subsection{Python3库实现的二分法 - bisect}
链接：https://docs.python.org/3/library/bisect.html
\begin{lstlisting}
bisect.bisect_left (a, x, lo=0, hi=len(a))
Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries.

The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.  The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo:i]) for the left side and all(val >= x for val in a[i:hi]) for the right side.

bisect.bisect_right (a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))
Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.

The returned insertion point i partitions the array a into two halves so that all(val <= x for val in a[lo:i]) for the left side and all(val > x for val in a[i:hi]) for the right side.
\end{lstlisting}

\subsection{LeetCode题}
\begin{table}[!htbp]
\centering
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    题目      & 难度                 \\
\midrule
0374 Guess Number Higher or Lower &   简单  \\
0852 Peek Index In a Mountain Array &  简单  \\
0033 Search in Rotated Sorted Array & 中等 \\
0034 Find First and Last Position of Element in Sorted Array & 中等 \\
0035 Search Insert Position & 简单 \\
\bottomrule
\end{tabularx}
\end{table}

%------------
\section{hashmap的使用}
hashmap查询的时间复杂度是$n(1)$，可以使用在很多需要查询的情况。
例如：
\begin{itemize}
\item 统计元素出现的次数
\item 判断一个元素是否出现过
\item 缓存之前的结果
\end{itemize}

\subsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}

    \toprule
        题目      & 难度                 \\
    \midrule
    0030 Substring with Concatenation of All Words & 困难  \\
    1743 Restore the Array From Adjacent Pairs & 中等 \\
    0036 Valid Sudoku & 中等 \\
    \bottomrule

\end{tabularx}
\end{table}

\section{数据结构 - 栈和队列}
\subsection{单调栈}
\subsubsection{基本定义}

单调栈是一种基于栈的数据结构，通过维护区间$[0, r]$数据的单调性，将时间复杂度从$O(n^2)$降为$O(n)$。单调性可以是单调递增或者是单调递减。

可能适用的场合：

\begin{itemize}
    \item 当数据存在单调性，用来查找下一个较大（较小）的值
    \item 定区间的最值
    \item 以该元素为最值的最大区间
\end{itemize}

\subsubsection{单调栈的代码实现}
\begin{lstlisting}[language=python]
class MStack:
    def __init__(self):
        self.stack = []

    def push(self, value):
        while self.stack and stack[-1] <= value:
            self.pop()
        self.stack.append(value)

    def pop(self):
        return self.stack.pop(-1)
\end{lstlisting}

\subsection{单调队列}

\subsubsection{基本定义}

按照先进先出的原则组织数据，同时保证队列中数据的单调性。适用范围：求滑动窗口的最值问题。

\subsubsection{单调队列的代码实现}
\begin{lstlisting}[language=python]
class MQueue:
    def __init__(self）:
        self.queue = []

    def push(self, value):
        while self.queue and self.queue[-1] < value:
            self.queue.pop(-1)
        self.queue.append(value)

    def pop(self):
        if self.queue:
            return self.queue.pop(0)
\end{lstlisting}


\subsection{优先队列（priority queue）}
\subsubsection{基本定义}
\begin{itemize}
    \item 普通队列是一种先进先出（FIFO）的数据结构，元素添加在队列尾，从队列头删除
    \item 优先队列里，元素被赋予优先级，当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先级先出（First In, Largest Out）的行为特征，通常采用堆来实现
\end{itemize}

\subsubsection{python的原生实现}
Python的库 heapq（Heap queue algorithm）提供了相关的功能。

heapq的链接https://docs.python.org/3.9/library/heapq.html。使用heapq需要注意的地方：
\begin{itemize}
    \item heapq使用list来初始化优先队列
    \item heapq实现了最小堆(min heap)，而不是最大堆(max heap)，通常我们用到的都是最大堆
    \item heap[0]和pop方法返回的是最小值
\end{itemize}

heapq的常用方法如下：

\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}

    \toprule
        Funcntion & 说明  \\
    \midrule
        heappush(heap, item)  & 将item加入到队列中  \\
        heappop(heap) & 弹出并且返回最小的item \\
        heappushpop(heap, item) & 将item压入队列中，并且弹出最小的Item，此方法的效率要比heappush和heappop的效率高 \\
        heapify(x) & 将list x初始化为heap，时间复杂度是线性的，$O(n)$级别 \\
    \bottomrule
\end{tabularx}
\end{table}
堆中保存的元素可以是元组，第一个元素是用来进行比较和排序的值（priority），第二个元素是真实的值。Python代码如下：

\begin{lstlisting}[language=python]
h = []
heappush(h, (5, "test value1"))
heappush(h, (4, "test value2"))
\end{lstlisting}

\subsubsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
    \toprule
        题目 & 难度                 \\
    \midrule
    0239 Sliding Window Maximum & 困难  \\
    0451 根据字符出现频率排序 & 困难 \\
    \bottomrule
\end{tabularx}
\end{table}

\section{数据结构 - 树}
\subsection{二叉树（Binary Tree）}

\subsubsection{基本定义}
二叉树是树形结构的重要类型。二叉树的特点是每个节点只能有两棵子树，且有左右之分。

\subsubsection{二叉树的遍历}
遍历是对树的一种基本运算，遍历二叉树就是按照一定的规则和顺序走遍二叉树的所有结点，使每个结点都被访问一次，而且只能被访问一次，遍历的实质是将二叉树的结点转换为一个线性序列来表示。访问方式按照访问根节点的次序来命名的。代码实现方式可以用递归的方式来实现。

\begin{itemize}
    \item 先序遍历 - 先访问根节点，然后访问左子树，最后访问右子树
    \item 中序遍历 - 先访问左子树，然后根结点，最后访问右子树
    \item 后序遍历 - 先访问左子树，然后访问右子树，最后访问根节点
\end{itemize}


\subsubsection{遍历的代码实现}
\begin{lstlisting}[language=python]
class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def traversal(node, result=[]):
    if node == None:
        return result

    # 向result添加val的操作和递归调用的先后次序决定遍历次序
    result.add(node.data) # 先序遍历
    traversal(node.left, result)
    # result.add(node.data) # 中序遍历
    traversal(node.right, result)
    # result.add(node.data) # 后序遍历

    return result
\end{lstlisting}

\subsubsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
    \toprule
        题目 & 难度                 \\
    \midrule
    剑指Offer 37 序列化二叉树 & 困难  \\
    \bottomrule
\end{tabularx}
\end{table}

\subsection{二叉搜索树}
\subsubsection{基本定义}
\begin{itemize}
    \item 可以是空树
    \item 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
    \item 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
    \item 它的左、右子树也分别为二叉排序树
\end{itemize}


\section{数据结构 - 图(Graph)}
\subsection{基本定义}
图是有一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点有时也成为节点，边也被成为链接。
图相关的一些概念：
\begin{itemize}
    \item 顶点和边
    \begin{itemize}
        \item 顶点（Vertex），通常用V来表示顶点集合
        \item 边（Edge)，通常用E来表示边的集合
    \end{itemize}

    \item 图可以分为有向图和无向图：
    \begin{itemize}
        \item (v, w)表示无向边，即v和w是互通的
        \item <v, w>表示有向边，该边始于v，终于w
    \end{itemize}

    \item 图可以分为有权图和无权图：
    \begin{itemize}
        \item 有权图：每条边具有一定的权重（weight）
        \item 无权图：每条边均没有权重，也可以认为每条边的权重是1
    \end{itemize}

    \item 图可以分为连通图和非连通图：
    \begin{itemize}
        \item 连通图：所有的顶点都有路径相通
        \item 非连通图：存在某两个顶点没有路径相连
    \end{itemize}

    \item 图的顶点还有度的概念：
    \begin{itemize}
        \item 度（Degree)：所有与它连接点的个数之和
        \item 出度（OutDegree）：在有向图里，所有从该顶点出的边数之和
        \item 入库（InDegree）：在有向图里，所有接入该顶点的边数之和
    \end{itemize}
\end{itemize}

\subsection{图的表示方法}
图的表示方法有两种：邻接矩阵（Adjacency Matrix）和邻接链表（Adjacency List）。
\begin{itemize}
    \item 邻接矩阵
    \begin{itemize}
        \item n个顶点的图需要一个$n \times n$的矩阵来表示
        \item 在无权图里，矩阵坐标的每个位置值为1表示两个点相连，0表示两个点不相连
        \item 在有权图里，矩阵坐标的每个位置值代表两个点之间的权重，0表示两个点不相连
        \item 在无向图中，邻接矩阵关于对角线相等
    \end{itemize}
    \item 邻接链表
    \begin{itemize}
        \item 对于每一个顶点，存储着一个链表，用来指向所有与该点直接相连的点
        \item 对于有权图，链表的结点要保存相连的顶点和到达该顶点的权重
    \end{itemize}
\end{itemize}

邻接矩阵占用空间较多，但是遍历查找方便；邻接链表会节省空间，但是查找会比较耗时。

\subsection{常见的算法}
\subsubsection{深度优先遍历，DFS}
\subsubsection{广度优先遍历，BFS}
\subsubsection{最短路径}
\subsubsection{最小生成树, Minimum Spanning Trees, MST}
\subsubsection{拓扑排序}

\section{基环树}
\subsection{基本概念}
基环树就是有n个点n条边的图，比树只出现了一个环，树上在加一条边，它形如一个环，每个连通块必定有且仅有一个环，环上每个点都有一棵子树的形式。


特殊形态的基环树有:
\begin{itemize}
    \item 无向树 N个点N条无向边
    \item 外向树 N个点，每个点只有一条入边，入度为1
    \item 内向树 N个点，每个点只有一条出边，出度为1
\end{itemize}
以上三种树中，可以将环作为根，就可以对每个环上的子树进行处理。
\subsection{常见算法}
\subsubsection{找环}

\subsection{LeetCode题}
\begin{table}[!htbp]
\centering
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    题目      & 难度                 \\
\midrule
5970 Maximum Employees to Be Invited to a Meeting & 困难  \\
\bottomrule
\end{tabularx}
\end{table}

\chapter{算法精研}
\section{回溯法}

\subsection{基本概念}
\begin{itemize}
    \item 实际上是一种暴力穷举的算法
    \item 穷举的过程是遍历一个多叉树的过程
    \item 会有重复计算的情况出现，需要根据条件进行剪枝，来减少计算量
    \item 使用回溯法的明显标记
    \begin{itemize}
    \item 排列、组合（子集、幂集、字符全排列）。 在传值时，对于排列问题，是要删掉单个用过的元素；组合问题，是删掉前面所有的元素
    \item 数组、字符串，给定一个特定的规则，尝试搜索迭代找到某个解
    \item 二维数组下的DFS搜索（八皇后、黄金矿工、数独）
    \end{itemize}
\end{itemize}
\subsection{代码框架}

\begin{lstlisting}[language=python]
result # 用来保存回溯结果
路径 # 题设的元素集合
def backtrack(路径，选择列表):
    # 进行结束条件的判断
    if 满足结束条件：
        # 保存结果
        result.add()
        return

    for 选择项 in 选择列表:
        # 判断【选择项】是否满足题设条件
        # 如果判断条件是否”全部元素都被处理“，结果就是全排列
        if 选择项不满足条件：
            continue

        做选择
        backtrack(路径，选择列表)
        撤销选择
\end{lstlisting}

\subsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
    \toprule
        题目 & 难度                 \\
    \midrule
    46 全排列 & 中等  \\
    1239 串联字符串的最大长度  & 中等 \\
    2140 解决智力问题 & 中等 \\
    2151 Maximum Good People Based on Statements & 困难 \\
    \bottomrule
\end{tabularx}
\end{table}

\section{广度优先搜索 - BFS}
\subsection{基本概念}
\begin{itemize}
    \item BFS和DFS一样，其实是一种搜索算法
    \item 搜索过程可以想象成是构建一颗树的过程，初始状态是根节点，然后每次是搜索处理同一级的所有子节点后，再处理下一级的子节点，直到所有子节点都处理完毕，完成对所有可能情况的处理
    \item 和DFS不同的地方是：DFS会沿着一条可能的路径处理子节点，直到处理完一种可能性，再处理另外的可能性
    \item BFS和DFS的区别:BFS通常是求最小的情况，DFS通常是求有没有的情况
\end{itemize}
\subsection{代码框架}

\begin{lstlisting}[language=python]
result # 用来保存回溯结果
路径 # 题设的元素集合
def bfs():
	# 初始化队列
    state_queue = List()
    # 加入初始化状态
    # state_queue里保存的state一般格式为[针对每个状态的Key, 步数]
    state_queue.append(init_state)
    # 用HashSet来保存处理过的状态，避免形成环
    # bfs的过程是一个生成有向无环图的过程
    visited_states = set()
    # 只要有状态就进行搜索
    while len(state_queue) > 0:
      	# 取出state
        current_state = state_queue.pop()
        # 得到每个状态的所有可能的下一个子状态insert
        child_states = get_next_children(state)

        # 处理每个子状态
        for child_state in child_states:
            # 跳过处理过的
            if child_state in visited_states:
                continue
            # 判断是否是符合条件的状态
            if is_bad_state(child_state):
                continue
            # 判断是否是要搜索的目标
            if is_target(child_state):
                # 返回值需要根据题意进行计算，通常是步数
                return
            visited_states.insert(child_state)
            state_queue.insert(0, child_state)
\end{lstlisting}

\subsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
    \toprule
        题目 & 难度                 \\
    \midrule
    0752 Open the Lock & 中等  \\
    0773 Sliding Puzzle  & 困难 \\
    0909 Snakes and Ladders & 中等 \\
    \bottomrule
\end{tabularx}
\end{table}

\section{动态规划}
\subsection{基本概念}
针对的典型问题

\begin{itemize}
    \item 求解的数量
    \item 求最大小值、满足条件的情况总数
    \item 求存在性
    \item 背包问题
    \item 股票问题
    \item 子序列问题
\end{itemize}

解题六步骤
\begin{itemize}
  \item 确定dp数组（dp table）以及下标的含义
  \item 确定递推公式（状态转移方程）
  \item dp数组如何初始化
  \item 确定遍历顺序，正序遍历还是逆序遍历
  \item 举例推导dp数组
  \item 最后结果的选取，需要根据题意来判断
\end{itemize}

其中，最难的步骤是第2步，容易出错的是第3步。第2步的核心是找到当前的问题dp[i]和之前的问题dp[i-j]之间的关系，j可以是变化的，也可以是1。也就是如何把当前问题转为之前问题的解的方法，形成递推。这个递推可以是向前递推也可以是向后递推。

\subsection{01背包问题}
\subsubsection{基本定义}
01背包问题的定义：有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力解的方法就是对于每个物品都有放和不放两种状态，用回溯法是可以解的，递归的伪代码如下，时间复杂度是$O(2^n)$
\begin{lstlisting}[language=python]
def process(array, cur_index, cur_state):
    state_use = cur_state + array[cur_index + 1]
    state_not_use = ...
    state = process(array, cur_index + 1, state_use)
    state += process(array, cur_index + 1, state_not_use)

def solution(array):
    result = self.process(array, 0, 0)
\end{lstlisting}
\subsubsection{解题方法}
\begin{itemize}
    \item dp数组为二维数组$dp[i][j]$(i表示物品，j表示背包容量)，表示从0-i的物品里任意选取放入容量为j的背包里，价值总和最大的值是多少
    \item 递推公式，需要考虑往背包里放或者不放第i件物品的两种情况
    \begin{itemize}
        \item 放，需要上一步的状态是背包里还可以放下第i件物品，即：$dp[i-1][j-weight[i]]$，放完之后的状态是$dp[i-1][j-weight[i]]+value[i]$
        \item 不放，即：$dp[i-1][j]$
        \item 两种情况取最大值即可，$dp[i][j]=max(dp[i-1][j-weight[i]] + value[i],dp[i-1][j])$
    \end{itemize}
    \item 初始化
    \begin{itemize}
        \item $dp[i][0] = 0$就是背包容量为0时，任何物品都放不进去，所以最大价值为0
        \item $dp[0][j]$的初始化
    \end{itemize}
\end{itemize}
\subsubsection{初始化}
\begin{lstlisting}[language=python]
# 逆序初始化
for j in range(bagWeight, -1, -1)：
    if j >= weight[0]:
        dp[0][j] = dp[0][j - weight[0]] + value[0]  # 初始化i为0时候的情况
# 顺序初始化
for j in range(bagWeight + 1):
        if j >= weight[0]:
            dp[0][j] = values[0]
        else:
            dp[0][j] = 0
\end{lstlisting}
\subsubsection{代码框架}
双重遍历
\begin{itemize}
    \item 第一重遍历物品
    \item 第一重遍历背包
\end{itemize}

\begin{lstlisting}[language=python]
# weights - 物品重量的数组
# values - 物品价值的数组
# bagWeight - 背包的总容量

# 求最大价值
object_count = len(object_array)

dp = [[0] * (bagWeight + 1) for _ in range(object_count)]

# 初始化第一行, 因为只有一个物品0号，所以只要背包容量能装下，每个物品只能使用一次，所以价值就是values[0]
# 初始化的方法也是由题意决定的，不是固定的
for j in range(bagWeight + 1):
    if j >= values[0]:
        dp[0][j] = values[0]

for i in range(1, object_count):
    for j in range(bagWeight + 1):
        not_used = dp[i - 1][j]

        used = 0
        if j >= object_array[i]:
            used = dp[i - 1][j - object_array[i]] + values[i]

        dp[i][j] = max(not_used, used)

return dp[object_count - 1][bagWeight]
\end{lstlisting}

\subsection{完全背包问题}
\subsubsection{一般定义}
\begin{itemize}
\item 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件 物品都有无限个(也就是可以放入背包多次)，求解将哪些物品装入背包里物品价值总和最大
\item 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件
\end{itemize}
\subsubsection{解题方法}
\begin{itemize}
    \item 双重遍历
        \begin{itemize}
        \item 第一重遍历物品
        \item 第二重遍历背包
        \end{itemize}
    \item 与01背包问题的解决方法的不同在于遍历背包的顺序不同
        \begin{itemize}
        \item 01背包问题是逆序遍历背包，由大到小
        \item 完全背包问题是正序遍历背包，由小到大
        \end{itemize}
    \item 使用二维数组代码框架
\end{itemize}
\subsubsection{代码框架}

\begin{lstlisting}[language=python]
# weights - 物品重量的数组
# values - 物品价值的数组
# bagWeight - 背包的总容量

# 求最大价值
object_count = len(object_array)
dp = [[0] * (bagWeight + 1) for _ in range(object_count)]
# 初始化第一行, 因为只有一个物品0号，所以只要背包容量能够整除
# 初始化的方法随题意变化，不固定

for j in range(bagWeight + 1):
    dp[0][j] = (weights[j] // object_array[0]) * values[0]

for i in range(1, object_count + 1):
    for j in range(0, bagWeight + 1):
        # 不是object_array[i]的情况
        not_used = dp[i - 1][j]
        # 使用object_array[i]的情况
        # 从使用1个object_array[i]开始，直到j无法放下object_array[i]为止
        used = 0
        k = 1
        while True:
            if j - k * object_array[i] >= 0:
                # 这一步是根据dp的定义来实现，这里是求最大价值
                used = max(used, dp[i - 1][j - k * object_array[i]])
                k += 1
            else:
                break
        dp[i][j] = max(not_used, used)

# answer能够放下的最大价值
answer = dp[object_count - 1][bagWeight]
\end{lstlisting}

\subsection{思考方法总结}
\begin{itemize}
\item 首先，了解题目的演算过程
\item 通过，从最后的整体效果看，判断题目可以转变为动态规划问题的哪一类子问题，然后再去构造dp数组和递推公式
\item 注意：
\begin{itemize}
  \item dp数组的值表示的含义会随题意变化，可以表示容量，也可以表示装完背包的物品选取的方案数，这时要注意调整递推公式里取值的方法
  \item 和容量有关，需要考虑取最大values[i]
  \item 和方案数有关，将使用物品的方案数和不使用物品的方案数相加
  \item 如果求组合数就是外层**for**循环遍历物品，内层**for**遍历背包
  \item 如果求排列数就是外层**for**遍历背包，内层**for**循环遍历物品
\end{itemize}
\end{itemize}

\subsection{Leetcode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
    \toprule
        题目 & 难度                 \\
    \midrule
    Offer 42. 求连续子数组的最大值 & 中等  \\
    0152 乘积最大子数组 & 中等 \\
    0055 Jump Game & 中等 \\
    2140 解决智力问题 & 中等 \\
    \bottomrule
\end{tabularx}
\end{table}

\section{归并排序 - Merge sort}
 \subsection{概念}
 归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

 归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
\begin{itemize}
     \item 分解（Divide）：将n个元素分成个含n/2个元素的子序列
     \item 解决（Conquer）：用合并排序法对两个子序列递归的排序
     \item 合并（Combine）：合并两个已排序的子序列已得到排序结果
\end {itemize}

 \subsection{代码框架}
 \subsubsection{递归法}
 \begin{lstlisting}[language=python]
# 排序
def merge(left, right):
    res = []
    while left and right:
        min_val = left.pop(0) if left[0] < right[0] else right.pop(0)
        res.append(min_val)
    res += left if left else right
    return res

# 递归拆分
def merge_sort(A):
    if len(A) <= 1:
        res = A
    else:
        mid = len(A) // 2
        left, right = merge_sort(A[:mid]), merge_sort(A[mid:])
        res = merge(left, right)
    return res
 \end{lstlisting}

\section{双指针（对撞指针）}
\subsection{基本概念}
指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用相反方向（对撞指针）的指针进行扫描，从而达到相应的目的，对撞指针遍历数组，然后根据题意并且结合数组有序产生的特性，来简化运算。双指针还有滑动窗口的应用。

\subsection{代码框架}
\begin{lstlisting}[language=python]
def dual_pointer(nums):
	left = 0
	right = len(nums) - 1:
	while left <= right:
		# do something ...

		left += 1
		right -= 1
\end{lstlisting}

\section{快慢指针}
\subsection{基本概念}
快慢指针也被称为 Hare Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。

该算法的应用场景：
\begin{itemize}
    \item 处理链表或数组中的循环的问题
    \item 找链表中点或需要知道特定元素的位置
\end{itemize}
快慢指针的原理是如果存在循环，那么快指针肯定会和慢指针相遇。

\subsection{LeetCode题}
\begin{table}[!htbp]
\centering
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    题目      & 难度                 \\
\midrule
    0141 Linked List Cycle &   简单  \\
    0142 Linked List Cycle II &   中等  \\
    0234 Palindrome Linked List &   简单  \\
    2141 Maximum Running Time of N Computers & 困难 \\
\bottomrule
\end{tabularx}
\end{table}

\section{贪心算法}
\subsection{基本概念}
贪心算法的基本思路就是通过局部的最优解来求得全局的最优解，没有固定的代码框架和套路。
解题时的基本步骤
\begin{itemize}
    \item 将问题分解为诺干子问题
    \item 找出适合的策略
    \item 求解每个子问题的最优解
    \item 将局部的最优解组合成全局的最优解
\end{itemize}

\subsection{LeetCode题}
\begin{table}[!htbp]
\centering
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    题目      & 难度                 \\
\midrule
0055 Jump Game &   中等  \\
\bottomrule
\end{tabularx}
\end{table}
%----------------------------------------------------------
\section{并查集 - UnionFind}
\subsection{基本概念}
主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
\begin{itemize}
\item 合并（Union）：把两个不相交的集合合并为一个集合，实质是修改一个元素的根元素
\item 查询（Find）：查询两个元素是否在同一个集合中，其实检查元素的根元素是否相同
\item 并查集的重要思想在于，用集合中的一个元素代表集合
\end{itemize}

\subsection{实现思路}
\begin{itemize}
    \item 用数组$fa[n]$表示n个元素，每个数组元素的值为他的父元素，如果父元素和该元素在数组的索引值相同，则这个元素就是根元素
    \item 查询一个元素的根元素可以用递归来实现，在查找过程中，可以进行路径压缩，就是将元素的父元素设置为它的根元素
    \item 按秩合并
    \begin{itemize}
        \item 秩，可以理解为子树的深度
        \item 用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。
    \end{itemize}
\end{itemize}

\subsection{代码框架}
\begin{lstlisting}[language=python]
fa = [n]
rank = [n]
def init():
    for i in range(n):
        fa[i] = i
        rank[i] = 1

def find(x):
    if fa[x] == x:
        return x
    else:
        fa[x] = find(fa[x])
        return fa[x]

def merge(i, j):
    x = find(i)
    y = find(j)

    if rank(x) <= rank(y):
        fa[x] = y
    else:
        fa[y] = x

    if rank[x] == rank[y] and x != y:
        rank[y] += 1

\end{lstlisting}

\subsection{LeetCode题}
\begin{table}[!htbp]
\centering
\begin{tabularx}{\textwidth}{lXXX}
\toprule
    题目      & 难度                 \\
\midrule
2092 Find All People With Secret &  困难  \\
2157 Groups of Strings & 困难 \\
\bottomrule
\end{tabularx}
\end{table}

\section{二维凸包（Convex Hull）算法}
\subsection{基本概念}
凸多边形是指所有内角大小都在$[0, \pi]$范围内的简单多边形，在平面上能包含所有给定点的最小凸多边形叫做凸包。
\subsection{算法}
解决二维凸包问题，主要有Jarvis步进算法(Jarvis March)，增量算法(Incremental Method)，快速凸包算法（Quick Hull），分而治之算法（Divide and Conquer），Graham扫描算法，单调链算法（Monotone Chain），Kirkpatrick–Seidel算法，chan算法。

\subsubsection{Jarvis步进算法}

\subsection{LeetCode题}
\begin{table}[!htbp]
    \centering
    \begin{tabularx}{\textwidth}{lXXX}
        \toprule
        题目      & 难度                 \\
        \midrule
        587 Erect the Fence &  困难  \\
        \bottomrule
    \end{tabularx}
\end{table}

%----------------------------------------------------------
\chapter{刷题记录}
\section{2021-05-23}
\subsection{0005 最长回文子串}
\begin{itemize}
    \item  难度：困难
    \item 第一次写动态规划，主要是探测算法的思考有困难
\end{itemize}

\subsection{0006 Z字符转换}
\begin{itemize}
  \item  难度：简单
  \item  按照题意的方式来写算法就可以
\end{itemize}

\subsection{0007 整数逆序}
\begin{itemize}
    \item 难度：中等
    \item 经典的算法
\end{itemize}

\subsection{1707 与数组中元素的最大异或值}
\begin{itemize}
    \item 难度：困难
    \item 暴力法可以解决，但是时间复杂度太高，不满足要求
    \item  字典树也是经典的算法，只是一般情况下不会接触到
\end{itemize}

\subsection{0008 字符串转化整数(atoi)}
\begin{itemize}
    \item 难度：中等
    \item 不难，按照题意写代码就行，主要是何时开始和结束，以及负号的处理
\end{itemize}

\section{2021-05-26}
\subsection{0664 奇怪的打印机}
\begin{itemize}
    \item 难度：困难
    \item 这种需要根据不断尝试最终找出最优解的问题，极大可能使用动态规划来解决
    \item 如何构造循环（从小到大循环，还是从大到小循环）需要看探测的公式需求来选择
\end{itemize}

\subsection{0009 回文数}
\begin{itemize}
    \item 难度：简单
    \item 转为字符串，遍历字符，比较两端的字符，不等的情况返回False，循环结束就返回True
\end{itemize}

\section{2021-05-28}
\subsection{0477 海明距离总和}
\begin{itemize}
    \item 难度：中等
    \item 最大的难度是想到1一个数去若干数的海明距离综合的快速求法
    \begin{itemize}
        \item 最容易想到的暴力解法，两个for循环，然后求出所有两两组合的海明距离，然后统计总和
        \item 如果从计算两个数的海明距离，然后统计所有的组合的总和，时间复杂度超标，统计异或的结果二进制里值为1的位的总和。
        \item 如果按照这个算法，时间复杂度是$O(N^2)$，数组长度为$10^4$，平方为$10^8$, 大概率会超时
    \end{itemize}
    \item 换个角度看，一个数和要比较的数，在某一位上的0或者1的数量为0，则这位上的海明距离为零。如果该位上，1和0的数量都不为零，则这位上的海明距离就是1和0的数量的乘积。按照此算法，遍历一次数组就可以得出一位的海明距离，时间复杂度为$O(n)$，如果数组里的数最大位数为m，那么总体的时间复杂度为$O(m * n)$, 因为m是最大整数的2次幂数，所以最终的算法复杂度为$O(n)$
\end{itemize}

\section{2021-05-29}
\subsection{560 和为k的子数组}
\begin{itemize}
    \item 难度：中等
    \item 暴力解的情况
    \begin{enumerate}
      \item 遍历所有连续子序列需要两个循环嵌套，时间复杂度$O(n^2)$
      \item 求每个子序列的元素和，需要一个循环，时间复杂度$O(n)$
      \item 比较和是否和目标值K相同，相同的时候计数，整体的时间复杂度是$O(n^3)$，肯定不满足要求
    \end{enumerate}
\end{itemize}
\subsubsection{暴力解的代码}
\begin{lstlisting}[language=python]
def subarraySumForce(self, nums: List[int], k: int) -> int:
    length = len(nums)
    count = 0
    for left in range(length):
        sums = 0 # sums 代表，left..right的元素和
        for right in range(left, length):
            sums += nums[right]
            if sums == k:
                count += 1

    return count
\end{lstlisting}

\subsubsection{逐步优化 - 利用前缀和来优化求连续子序列的和}
\begin{itemize}
    \item 考虑是否可以减少循环的嵌套层数，先考虑计算连续子序列的和，是否可以不用循环
    \begin{itemize}
        \item array - 表示输入的数组
        \item p[i] - 表示数组从第1个元素到第i个元素的子序列和，p[0] = 0, i从1开始，到n结束，n为数组长度
        \item p[i+1] - 就是 p[i] + array[i]
        \item 通过一个循环就可以求得，任意[0..i]的序列元素和
    \end{itemize}

    \item 那么索引i到索引j的序列元素和如何求？
    \begin{itemize}
        \item s[i..j] 表示array中索引i到索引j的序列和
        \item 举例看看：
        \begin{itemize}
          \item array = [0, 1, 2, 3, 4, 5], 如何求s[1..3]
            \item 其实是求array[1], array[2], array[3]的和
            \item 我们现在已经有的结果是$p[i](i= 0..6)$，p[i]表示array数组从索引0到索义i-1的序列和
              \item p[1] = sum(array[0])
              \item p[4] = sum(array[0], array[1], array[2], array[3])
              \item s[1..3] = p[4] - [0]
            \item 所以，推出公式：s[i..j] = p[j+1] - p[i]
        \end{itemize}
        \item 由此得出，只要计算出P，就可以求出所有子序列的元素和，那么暴力解中第二步的循环就可以省去
    \end{itemize}
    \item 单独使用前缀和的方法，时间复杂度为$O(n^2)$
\end{itemize}
\subsubsection{采用前缀和的解题代码}
\begin{lstlisting}[language=python]
def subarraySumPresum(self, nums: List[int], k: int) -> int:
    length = len(nums)
    count = 0
    presum_array = [0] * (length + 1)   # 前缀和数组，presum_array[i]代表前i个元素的和，总长度为length + 1

    for i in range(0, length):
        presum_array[i+1] = presum_array[i] + nums[i]

    for i in range(length):
        for j in range(i, length):
            if presum_array[j + 1] - presum_array[i] == k:
                count += 1

    return count
\end{lstlisting}

\subsubsection{逐步优化 - 利用Hashmap}
从前缀和的算法可锝，如果$s[i..j] == k$就是满足条件的子序列，即当$p[j+1] - p[i] == K$，也就是当$p[i] == p[j+1] - K$就是满足条件的情况（j从0到n-1）。这样在计算出$P[j+1]$的值后，去判断是否之前出现过某个子序列的值$P[j+1]- K$
\begin{itemize}
    \item 如果出现过，那么满足条件的次数就增加出现的次数，同时，更新出现的次数。
    \item 如果没有满足就将$P[j+1] - K$的值保存起来，并且出现的次数+1，以后备查。这个保存和备查可以用hash字典来实现。这样只要计算一遍P就可以完成全部的统计工作。
    \item 需要注意的是，hashmap的初始化值需要有{0, 1}，表示如果$P[i] == K$时的初始情况
\end{itemize}
\subsubsection{利用Hashmap进一步优化的代码}
\begin{lstlisting}[language=python]
def subarraySum(self, nums: List[int], k: int) -> int:
    length = len(nums)
    count = 0
    pre = 0

    dict: Dict[int, int] = {0: 1}

    for i in range(0, length):
        pre = pre + nums[i]     # 求P[i]
        if dict.get(pre - k, None):
            count += dict.get(pre - k)
        dict[pre] = dict.get(pre, 0) + 1

    return count
\end{lstlisting}

\subsection{1074 元素和为目标值的子矩阵数量}
\begin{itemize}
\item 难度：困难
\item 题意分析：
\begin{itemize}
\item 输入矩阵m，目标值K，求子矩阵的所有元素的和为K的数量
\item 从题意可知，需要求得所有子矩阵的元素和，与目标值进行判断，统计相等的数量
\end{itemize}

\item 解题需要解决的子问题

\begin{itemize}
    \item 枚举子矩阵，求子矩阵的元素和
    \item 从枚举子矩阵这个行为就很容易推想到是否可用动态规划来处理
    \begin{itemize}
    \item 需要考虑合适的状态方程
    \item 根据状态方程来判断遍历的顺序
    \end{itemize}
    \item 尝试结果：推导状态方程不成功，换思路，无思路，看题解
\end{itemize}
\end{itemize}

\subsubsection{题解分析}
读题解知道此问题可以转换为问题0560，于是开始解问题0560，就有了前面的分析。
有0560的基础后，如何处理此问题呢？考虑如下情况，矩阵$m[3x3]$
$$
m=\left[
\begin{matrix}
1 & 2 & 3 \\
3 & 4 & 5 \\
7 & 8 & 9
\end{matrix}
\right]
$$
\begin{itemize}
    \item 对第一行使用0560的方法，可以得到子矩阵在第一行的结果
    \item 如果对第一行和第二行的和组成的新行运用0560的方法，可以得到子矩阵在第一行和第二行的结果
    \item 整个矩阵的子矩阵，其实就是从矩阵的每一行开始，通过0560方法计算本行，然后与后续行求和后，通过0560方法计算，直到最后一行，所有的和累加就是最后的结果
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
    count = 0
    m = len(matrix)     # 行数
    n = len(matrix[0])  # 列数

    for i in range(0, m):
        line_value = [0] * n
        for j in range(i, m):
            for k in range(0, n):
                line_value[k] += matrix[j][k]   # 累加下一行
            count += self.subarraySum(line_value, target)

    return count
\end{lstlisting}

\subsection{0010 正则表达式匹配}
\begin{itemize}
\item 难度：困难
\item 题意：检查由小写字母和‘.’和‘*’组成的正则表达式是否可以表示输入的字符串
\item 解题思路：解题方法应该是逐步比较，不断第尝试正则表达式中的表达式是否能够表示字符串，应该大概率是用动态规划来解决
\end{itemize}

\subsubsection{动态规划解题}
dp数组为dp[i][j]，初始化dp[0][0] = True，表示s和p都为空字符串时，匹配结果是True。s代表输入的字符串，p代表输入的正则表达式；dp[i][j]表示s[0..i]的子串是否可以被p[0..j]的表达式所表示。

状态转移方程分析如下：
\begin{enumerate}
\item $p[j]$为普通字符时
\begin{itemize}
    \item 如果$s[i]==p[j]$，$dp[i][j]=dp[i - 1][j - 1]$
    \item 如果$s[i]!=p[j]$，$False$
\end{itemize}

\item $p[j]$为“.”时
\begin{itemize}
    \item 无论$s[i]$和$p[j]$是否相等，$dp[i][j]=dp[i - 1][j - 1]$
\end{itemize}

\item $p[j]$为“*”时
\begin{itemize}
    \item 当$s[i]=p[j-1]$，$dp[i][j]=dp[i - 1][j] or dp[i][j-2]$
    \item 当$s[j-1]!=p[j-1]$，$dp[i][j]=dp[i][j-2]$
\end{itemize}
\end{enumerate}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def isMatch(self, s: str, p: str) -> bool:
    def match(i: int, j: int) -> bool:
        if i == 0:
            return False
        if p[j - 1] == '.':
            return True
        return s[i - 1] == p[j - 1]

    n = len(p)
    m = len(s)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] |= dp[i][j - 2]
                if match(i, j - 1):
                    dp[i][j] |= dp[i - 1][j]
            else:
                if match(i, j):
                    dp[i][j] |= dp[i - 1][j - 1]

    return dp[m][n]
\end{lstlisting}

\section{2021-05-30}
% template - 题解
\subsection{0012 整数转罗马数字}
\begin{itemize}
    \item 难度：中等
    \item 题意分析：给一个整数，返回罗马数字的字符串
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 按照整数转字符串的算法，依次获取最右边的数字，然后根据数字的位数，转换成实际的整数
    \item 个位：0-9
    \item 十位：10-90
    \item 百位：100-900
    \item 千位：1000-4000
    \item 处理0的情况
    \item 然后根据上面得到的值，查表得到对应的罗马数字，拼接上字符即可
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def intToRoman(self, num: int) -> str:
    # 这里用字典来完成数字到基本罗马数字的转换
    val_dict : Dict = {
        1: 'I',
        2: 'II',
        3: 'III',
        4: 'IV',
        5: 'V',
        6: 'VI',
        7: 'VII',
        8: 'VIII',
        9: 'IX',
        10: 'X',
        20: 'XX',
        30: 'XXX',
        40: 'XL',
        50: 'L',
        60: 'LX',
        70: 'LXX',
        80: 'LXXX',
        90: 'XC',
        100: 'C',
        200: 'CC',
        300: 'CCC',
        400: 'CD',
        500: 'D',
        600: 'DC',
        700: 'DCC',
        800: 'DCCC',
        900: 'CM',
        1000: 'M',
        2000: 'MM',
        3000: 'MMM',
        0:''
    }
    ans = ''
    val = 0
    while num > 0:
        digit = num % 10
        real_digit = digit * 10 ** val
        ans = val_dict[real_digit] + ans
        val += 1
        num = num // 10

    return ans
\end{lstlisting}


\section{2021-06-02}
% template - 题解
\subsection{0523 连续子数组和}
\begin{itemize}
    \item 难度：中等
    \item 题意分析：给定一个整数数组nums和一个整数target，要求判断nums里是否有一个子数组满足如下的条件
    \begin{itemize}
        \item 子数组长度至少为2
        \item 子数组内元素的和为target的倍数
    \end{itemize}
    \item 如果存在返回True，否则返回False
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 此题和0560题类似，可以用前缀和和hash表来解
    \item 0523问题是用前缀和用来解决子数组和，而0560问题是子数组和能够整除K，前缀和是$P[i..j]=P[j]-P[i]$，如果P[i..j]可以整除K，也就是P[i],P[j]的除以K的余数相同，问题转化为通过前缀和查找相同余数的过程
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    length = len(nums)
    if length < 2:
        return False
    remainder = 0
    dict: Dict[int, int] = {0: -1}
    # -1, 避免nums[0]能够整除k，但是元素个数为1的情况

    for i in range(0, length):
        remainder = (remainder + nums[i]) % k     # 求P[i]
        if dict.get(remainder) is not None:
            index = dict[remainder]
            if i - index >= 2:
                return True
        else:
            dict[remainder] = i

    return False
\end{lstlisting}

\section{2021-06-03}

% template - 题解
\subsection{0494 目标和}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 最开始的时候考虑过是否可以用动态规划来解，但是递归DFS是一个很自然的解法，就用递归来解的，但是超时了。看了官方解也是递归的解法
    \item 递归解法的时间复杂度：每个元素会有2种可能，n个元素需要计算2\^n的可能，所以时间复杂度为O(2\^n)
    \item DFS的优化可以用记忆法来优化，保存已经搜索过的记录，避免重复计算
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
# 解题的方法，命名和Leetcode的保持一致即可
def process(self, nums, curr_index, target, sum):
    key = str(curr_index) + '_' + str(sum)
    value = self.dfs_dict.get(key, None)
    if value:
        return value

    if curr_index == len(nums):
        if sum == target:
            self.dfs_dict[key] = 1
            return 1
        else:
            self.dfs_dict[key] = 0
            return 0
    else:
        next_index = curr_index + 1
        left = self.process(nums, next_index, target, sum + nums[curr_index])
        right = self.process(nums, next_index, target, sum - nums[curr_index])
        self.dfs_dict[key] = left + right
        return left + right

def findTargetSumWays(self, nums: List[int], target: int) -> int:
    self.dfs_dict.clear()
    return self.process(nums, 0, target, 0)
\end{lstlisting}

\section{2021-06-12}
连续试了几道动态规划的题目，看来需要重新学习动态规划，开始刷动态规划的题目，从简单的开始，将LeetCode的相关题目刷一刷。

% template - 题解
\subsection{0096 不同的二叉搜索树}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 题意是构建[1..n]的n个数字为节点来构建二叉搜索树，这样的二叉搜索树的数量
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
递推公式是难点。
\begin{itemize}
    \item 构建二叉搜索树的方法是：以[1..n]中的数字i为根节点，然后左子树为[1..i-1]的数字组成的二叉搜索树，右子树为[i+1..n]的数字组成的二叉搜索树，总数量是左子树的数量和右子树数量的乘积，i可以是1到n中的任意数
    \begin{itemize}
        \item dp[n]表示用[1..n]的数字构建的二叉搜索树的数量
        \item 以[1..i-1]的数字组成的二叉搜索树的数量为dp[i-1]
        \item 以[i+1..n]的数字组成的二叉搜索树的数量为dp[n-i]
    \end{itemize}
\end{itemize}
$$
dp[n] = \sum_{i=1}^{n}{dp[i-1] * dp[n-i]}
$$

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def numTrees(self, n: int) -> int:
    dp = [0] * (n + 1)  # dp[i]表示由1到i的数字组成的不同的二叉搜索树的数量
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        for j in range(1, i + 1):
            dp[i] += dp[j - 1] * dp[i - j]
    return dp[n]
\end{lstlisting}

\subsection{0416 分割等和子集}

\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 如果数组所有元素的和$sum$为奇数，则返回false
        \item  如果数组所有元素的和$sum$为偶数，那么问题转化为是否可以在数组中找到一些元素，他们的和为数组元素和的一半。如果将数组的元素考虑成物品，那么背包的容量就是数组元素和的一半$sum/2$。此问题已经转换为01背包问题，数组里的元素只能用一次，判断是否可以用数组中的元素装完容量为$sum/2$。
        \item 这时还需要考虑，数组中最大元素如果大于$sum/2$，则返回false
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
此题属于01背包问题。
\begin{itemize}
    \item 设计dp数组
    \begin{itemize}
        \item $dp[i][j]$为表示从0到第i个元素是否可以装完容量为j的背包，$dp[n][sum/2]$就是答案
    \end{itemize}
    \item 递推公式
    \begin{itemize}
        \item 不放第i个元素，$如果dp[i-1][j]=true,则dp[i][j]=true$
        \item 放第i个元素，$如果dp[i-1][j-value[i]]=true, 则dp[i][j]=true$
    \end{itemize}

  \item 初始化dp
  \begin{itemize}
      \item 二维数组默认值都是False
      \item $dp[0][j]$，$dp[0][values[0]] = true $
      \item $dp[i][0]$, $dp[i][0]=true$, 表示背包容量为0，即什么都不放，这个条件可以达成，设置为true
  \end{itemize}

\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def canPartition(self, nums: List[int]) -> bool:
    nums_sum = sum(nums)
    max_target = max(nums)

    if nums_sum % 2 == 1:
        return False

    target = nums_sum // 2
    if max_target > target:
        return False

    nums_count = len(nums)
    dp = [[False] * (target + 1) for _ in range(nums_count)]

    dp[0][nums[0]] = True

    for i in range(nums_count):
        dp[i][0] = True

    for i in range(1, nums_count):
        for j in range(1, target + 1):
            if dp[i-1][j]:
                dp[i][j] = True
            elif j >= nums[i] and dp[i-1][j - nums[i]]:
                dp[i][j] = True

            if j == target and dp[i][j]:
                return True

    return dp[nums_count - 1][target]
\end{lstlisting}

\section{2021-07-04}
\subsection{0645 错误的集合}
\begin{itemize}
\item 难度：简单
\item 题意分析：给定一个数组，里面包含1到n的数字，但是有一个数字是被其他的数字覆盖了，要找出数组重复的一个数字，和被覆盖的真实数字。要求返回值是一个数组，索引0是重复的数字，索引1是真实的数字。
\item 解题思路：通过字典来保存数组里每个数字出现的个数，然后从1到n遍历字典，如果次数为2的就是重复的，字典里没有的数字就是真实的数字
\end{itemize}
\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def findErrorNums(self, nums: List[int]) -> List[int]:
    nums_dict = {}
    for i in range(len(nums)):
        nums_dict[nums[i]] = nums_dict.get(nums[i], 0) + 1

    ans = [0, 0]
    value_real = -1
    value_dup = -1
    for key in range(1, len(nums) + 1):
        value = nums_dict.get(key, -1)
        if value == -1:
            value_real = key
        if value == 2:
            value_dup = key
        if value_real != -1 and value_dup != -1:
            ans[0] = value_dup
            ans[1] = value_real
            break

    return ans
\end{lstlisting}

\section{2021-07-05}
\subsection{0726 原子的数量}
\begin{itemize}
\item 难度：困难
\item 题意
\begin{itemize}
    \item 给定一个字符串用来表达化学方程式，要求返回一个字符串，格式是：元素+元素的数量，元素按照字典顺序排列，如果元素的数量为1，则不包含数字1
    \item 输入字符串的格式
    \begin{itemize}
    \item 元素由大写和小写字母组成，如果后面没有数字，则该元素的数量为1
    \item 元素可以被括号“（）”包裹，右括号后面可以跟数字，表示括号内的化学方程式的整体数量，如果没有数字，就表示括号内的化学方程式的数量为1
    \end{itemize}
\end{itemize}
\end{itemize}

\subsubsection{解题思路}
遍历输入的字符串，会碰到五种字符：字母，数字，左括号，右括号;不同的字符有不同处理。字符串包含括号，需要进行消除括号的操作，这个操作非常类似处理算术表达式的方法，可以借助栈来完成。
\begin{itemize}
    \item 数字，就拼接成只包含数字的字符串
    \item 如何判断一个元素的截止：碰到大写字母，碰到括号
    \item 压栈操作
    \begin{itemize}
        \item 读取的元素和对应的数量，压入栈
        \item 读取到左括号，压入栈
        \item 读取到右括号，压入栈
    \end{itemize}
    \item 进行弹出栈操作的时机，当碰到大写字母，左括号，右括号时，如果这时栈顶元素是右括号，则开始弹栈操作，针对弹出的元素，用在右括号之后读取的数量乘以元素的原有数量，然后保存起来。如果弹出的是左括号，说明本次的括号处理完毕，将之前保存的元素和数量再次压入栈中。
    \item 当字符串都处理完后，要判断栈顶是否还有右括号。有的话，要进行弹栈处理。
\end{itemize}

字符串中所有的字符都处理完之后，栈内保存的是元素和对应的数量。这时，可能存在相同的元素，可以利用dict，将元素作为key，数量作为value，进行合并操作；然后对dict的keys进行升序排序，就得到了字典排列的keys，正序遍历排序后的keys，从dict取出对应元素的数量，按照题目要求拼接字符串即可。

\subsubsection{解题代码}
本题解使用到之前的Stack类来完成栈的操作。

\begin{lstlisting}[language=python]
def countOfAtoms(self, formula: str) -> str:
    def handle_pop_stack(atom_stack: Stack, atom_number_str: str) -> bool:
        if atom_stack.size() == 0:
            return False

        if atom_number_str == '':
            atom_number_str = '1'

        atom_number = int(atom_number_str)
        temp_atoms = []
        top = atom_stack.top()
        if top[0] == ')':
            while atom_stack.size() > 0:
                pair = atom_stack.pop()
                if pair[0] == ')':
                    continue
                elif pair[0] == '(':
                    for item in temp_atoms:
                        atom_stack.push(item)
                    return True
                else:
                    new_pair = (pair[0], pair[1] * atom_number)
                    temp_atoms.append(new_pair)
            return True
        else:
            return False

    # isupper, 是否为大写
    # isdecimal, 是否为数字
    atom = ''
    number_str = ''
    stack = Stack()

    for i in range(len(formula)):
        ch = formula[i]
        if ch.isupper():
            if handle_pop_stack(stack, number_str) is True:
                number_str = ''
                atom = ''

            if atom == '':
                atom = ch
            else:
                if number_str == '':
                    number_str = '1'
                stack.push((atom, int(number_str)))
                atom = ch
                number_str = ''
        elif ch.isdecimal():
            number_str += ch
        elif ch == '(':
            if handle_pop_stack(stack, number_str) is True:
                number_str = ''
                atom = ''

            if atom != '':
                if number_str == '':
                    number_str = '1'
                stack.push((atom, int(number_str)))
                atom = ''
                number_str = ''
            stack.push(('(', 0))
        elif ch == ')':
            if handle_pop_stack(stack, number_str) is True:
                number_str = ''
                atom = ''
            if atom != '':
                if number_str == '':
                    number_str = '1'
                stack.push((atom, int(number_str)))
                atom = ''
                number_str = ''
            stack.push((')', 0))
        else:
            atom += ch

    if atom != '':
        if number_str == '':
            number_str = '1'
        stack.push((atom, int(number_str)))
    else:
        if number_str != '':
            handle_pop_stack(stack, int(number_str))

    atom_dict = {}
    while stack.size():
        atom = stack.pop()
        if atom[0] == '(' or atom[0] == ')':
            continue
        atom_dict[atom[0]] = atom_dict.get(atom[0], 0) + atom[1]

    atoms = atom_dict.keys()
    atoms = sorted(list(atoms))

    ans = ''
    for key in atoms:
        number = atom_dict[key]
        if number == 1:
            ans += key
        else:
            ans += key
            ans += str(number)

    return ans
\end{lstlisting}

\section{2021-07-06}
\subsection{1418 点菜展示表}
\begin{itemize}
\item 难度：中等
\item 题意分析: %
题目给定一个二维数组，里面是客户点菜的记录，格式是[“客户名称”，“餐桌号”，“菜品名称”]。要求返回一个二维数组，内容是每个餐桌上的菜品的数量统计。返回数组的第一条记录的格式为[“Table”，“菜品1”，“菜品2”，“菜品3”...列出所有的菜品]，其他元素的格式为[“餐桌号”，“菜品1的数量”，“菜品2的数量”...]，要求菜品是按照字典顺序排列，餐桌按照餐桌号升序排列。
\end{itemize}
\subsubsection{解题思路}
遍历输入数组，针对每条记录进行处理。处理过程中，会涉及大量的查询，所以可以用dict来优化查询。本题难度是中等，如果对Dict的使用比较熟练的话，其实还是比较简单的。
\begin{itemize}
    \item 用dict来统计所有的菜品，菜品可以作为key，对所有输入记录处理完后，就可以得到全部的菜品
    \item 用dict来保存每张餐桌上的菜品和对应数量，餐桌上的菜品和对应数量也用dict来保存
    \item 因为后序要对餐桌号排序，所以餐桌号用整数
\end{itemize}

\subsubsection{解题代码}
主要是使用了字典dict来完成餐桌，菜品的检索和数量统计。

\begin{lstlisting}[language=python]
def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
    foods_dict = {}
    table_food_dict = {}

    for item in orders:
        foods_dict[item[2]] = foods_dict.get(item[2], 0) + 1
        table_id = int(item[1])
        if table_food_dict.get(table_id, None) is None:
            table_order = {item[2]: 1}
            table_food_dict[table_id] = table_order
        else:
            table_order = table_food_dict.get(table_id)
            table_order[item[2]] = table_order.get(item[2], 0) + 1

    row = ["Table"]
    foods_list = sorted(foods_dict.keys())
    for food in foods_list:
        row.append(food)

    ans = [row]

    table_ids = sorted(table_food_dict.keys())
    for key in table_ids:
        row = [str(key)]
        table_order = table_food_dict[key]
        for food in foods_list:
            row.append(str(table_order.get(food, 0)))

        ans.append(row)

    return ans
\end{lstlisting}


\section{2021-07-07}
\subsection{1711 大餐计数}
\begin{itemize}
\item 难度：中等
\item 题意分析:
\begin{itemize}
    \item 给定一个整数数组，数组中的第i个元素的值代表该道菜的美味程度。将任意两道不同的菜组成新的组合，菜品的美味程度的和等于2的幂，这样的组合成为大餐。
    \item 不同的索引就是不同的菜品
    \item 大餐的数量可能是个很大的值，需要做$10^9+7$取余的处理
    \item 每道菜的美味程度不大于$2^{20}$，也就是说每道大餐的美味程度不超过$2^{21}$
\end{itemize}
\end{itemize}

\subsubsection{解题思路}

\begin{itemize}
    \item 此题的目的就是在数组中两个元素的和为2的幂，这样的组合的个数
    \item 两数的和不会超过$2^{21}$，所以有22中可能，从0，2，4，...，$2^{21}$
    \item 可以用dict来优化查询，key是美味程度，value是该美味程度出现的次数
    \item 算法如下：
    \begin{enumerate}
        \item 遍历数组delicousness
        \item 得到一道菜品的美味程度meal
        \item 计算能够组成大餐的另外一道菜品meal pair的美味程度
        \item 如果字典dict中存在meal pair，就说明存在这样的大餐组合，大参的数量增加meal pair对应的value
        \item 如果dict中有meal pair，就说明存在这样的大餐，大参的数量增加meal pair对应的value
        \item 查询完所有可能的meal pair后，meal出现的次数加1
    \end{enumerate}
\end{itemize}

\subsubsection{解题代码}

\begin{lstlisting}[language=python]
def countPairs(self, deliciousness: List[int]) -> int:
    meal_dict = {}
    mod = 10 ** 9 + 7
    ans = 0
    for i in range(len(deliciousness)):
        meal = deliciousness[i]

        for k in range(1, 22):
            pair = 2 ** k - meal
            if pair < 0:
                continue
            if meal_dict.get(pair, -1) != -1:
                ans += meal_dict[pair]
        meal_dict[meal] = meal_dict.get(meal, 0) + 1

    return ans % mod
\end{lstlisting}

\subsection{31 下一个排列}
\begin{itemize}
\item 难度：中等
\item 题意分析: 给一个整数的数组，要求给出下一个更大按照字典排序的数组来。如果当前数组是最大一个字典排列，就返回最小的排列。
\end{itemize}
\subsubsection{解题思路}
\begin{itemize}
    \item 先找出最大的索引k满足$nums[k] < nums[k+1]$，如果不存在，就翻转整个数组
    \item 再找出另一个最大索引$l$满足$nums[l] > nums[k]$
    \item 交换$nums[l]$和$nums[k]$
    \item 最后翻转$nums[k+1:]$
\end{itemize}
注：此题完全没有思路，相关的分析和思路都是copy leetcode上牛人的帖子。
\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    def reverse(nums, i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    first_index = -1
    n = len(nums)
    for i in range(n-2, -1, -1):
        if nums[i] < nums[i+1]:
            first_index = i
            break

    if first_index == -1:
        reverse(nums, 0, n - 1)
        return

    second_index = -1
    for i in range(n - 1, first_index, -1):
        if nums[i] > nums[first_index]:
            second_index = i
            break
    if second_index != -1:
        nums[first_index], nums[second_index] = nums[second_index], nums[first_index]
        reverse(nums, first_index + 1, n - 1)
\end{lstlisting}

\section{2021-07-09}
\subsection{17.10 主要元素}
\begin{itemize}
    \item 难度：简单
    \item 题意分析：在一个整数数组里，如果其中某个元素出现的次数超过数组长度的一半，这个元素就是主要元素。题的要求是求出给定一个整数数组中的主要元素，如果不存在就返回-1。
\end{itemize}
\subsubsection{解题思路}
解题分为两步，每步都是一个for元素，遍历数组里的元素。整体的时间复杂度是$O(n)$。
\begin{enumerate}
    \item 求出占比最大的元素
    \begin{enumerate}
        \item count用来保存出现的次数，candidate用来保存出现的元素。
        \item 遍历数组里的元素，如果count等于0，代表目前还没有保存出现的元素，就将nums里的元素保存在candidate。如果nums里的元素等于candidate就将count加一，否则count减一。
        \item 当遍历完nums后，candidate保存的就是nums里占比最大的元素。
    \end{enumerate}
    \item 求出占比最大元素的出现次数，如果超过一般返回该元素，否则返回-1
\end{enumerate}
\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def majorityElement(self, nums: List[int]) -> int:
    count = 0
    candidate = -1

    for num in nums:
        if count == 0:
            candidate = num

        if candidate == num:
            count += 1
        else:
            count -= 1

    count = 0
    for num in nums:
        if num == candidate:
            count += 1

    if count * 2 > len(nums):
        return candidate
    else:
        return -1
\end{lstlisting}

\subsection{32.最长有效括号}

\begin{itemize}
    \item 难度：困难
    \item 题意分析

    \begin{itemize}
        \item 给定一个只包含左括号“(”和右括号“)”的字符串，要求返回连续正确有效的括号字符串的长度
    \end{itemize}

\end{itemize}

\subsubsection{解题思路}

\begin{enumerate}
    \item 判断是否为正确字符串
    \item 统计连续字符串的长度
    \item 可以利用栈来完成字符串的解析，遍历整个字符串，如果是左括号就压栈，如果是右括号就弹出栈顶元素
    在字符串遍历结束后，保存的最大值即为答案\begin{enumerate}
        \item 如果是左括号，说明现在碰到一个有效的括号字符串，就压入数字2。这时需要考虑栈内的元素可能是这种情况：['(','2',...]，这时需要合并栈顶开始的连续数字，合并后为['(','4',...]
        \item 如果是数字，就说明可能碰到这种情况['(','2',...],这时弹出数字，然后判断后面的元素是否为左括号, 就将之前的数字加2，再次压入栈中，然后合并从栈顶开始连续的数字
        \item 如果是右括号，就将元素再次压栈
        \item 依次处理每个元素，在处理每次合并栈内的数字时，保存最大值
    \end{enumerate}
\end{enumerate}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def longestValidParentheses(self, s: str) -> int:
    # 合并stack里的连续数字
    def merge_number(stack, count):
        while stack.size():
            temp = stack.pop()
            if temp.isdigit():
                count += int(temp)
            else:
                stack.push(temp)
                break
        stack.push(str(count))
        return count
    #主逻辑
    stack = Stack()
    ans = 0

    for ch in s:
        if ch == ")":
            count = 0
            if stack.size() > 0:
                top = stack.pop()
                if top == '(':
                    count += 2
                    count = merge_number(stack, count)
                    ans = max(count, ans)
                elif top.isdigit():
                    count += int(top)
                    if stack.size() > 0:
                        temp = stack.pop()
                        if temp == '(':
                            count += 2
                            ans = max(count, ans)
                            stack.push(str(count))
                            count = 0
                            count = merge_number(stack, count)
                            ans = max(count, ans)
                        else:
                            stack.push(temp)
                else:
                    stack.push(top)
        else:
            stack.push(ch)

    return ans
\end{lstlisting}

\section{2021-07-10}

\subsection{981 Time Based Key-Value Store}
\begin{itemize}
    \item 难度：中等
    \item 编写一个基于时间的键值对类TimeMap，提供如下的两个操作
    \begin{itemize}
        \item set(string key, string value, int timestamp) \newline 存储key，value，时间戳 timestamp
        \item get(string key, int timestamp)
        \begin{itemize}
            \item 返回之前存储的key，value，timestamp0，其中timestamp小于之前保存时的timestamp0
            \item 如果不存，返回空字符（“”）
            \item 如果存在多个满足条件的值，返回timestamp最大的值
        \end{itemize}
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\textbf{关键字：dict，二分法}。
\begin{itemize}
    \item 本题基本上保存和查询key和value的键值对，Python的dict可以满足要求，从题意可以看出，对于同一个（key，value）对，会对应不同的timestamp，那么利用dict来保存的value，应该是包含value和timestamp的。在查询时，还要返回比查询的timestamp小的最大值，那么就要解决如何有序保存value和timestamp了
    \item 可以用list来保存value和timestamp的元组“(timestamp, value)”，并且需要按照timestamp进行排序，从题意可知，所有set操作中timestamp是严格按照递增出现的，所以保存到list里时，就是排好序的
    \item set操作 \newline
    首先从dict里得到key对应的list，然后将value和timestamp的元组添加到list的尾部，这样list里就是按照timestamp递增的顺序排列
    \item get操作 \newline
    首先从dict里得到key对应的list，如果为空，则返回“”。查找元素可以用二分法来实现（bisect.bisect），由于list是按照升序排列的，bisect返回的i就是满足题意的最大的timestamp所配对的value对应的索引，需要注意bisect返回的下标是从1开始的，值为-1时，代表没有找到
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
class TimeMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.value_dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.value_dict[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        value_list = self.value_dict[key]
        if len(value_list) == 0:
            return ""

        # 从题意可以，value都是由小写字母组成，长度最长为100，所以101个"z"的字符串是最大值。
        # 这样(timestamp, "z" * 101)的比较结果就由timestamp来决定
        index = bisect(value_list, (timestamp, "z" * 101))

        if index > 0:
            return value_list[index - 1][1]
        else:
            return ""
\end{lstlisting}

\subsection{33 SearchInRotatedSortedArray}
\begin{itemize}
    \item 难度：中等
    \item 题意分析
    \begin{itemize}
    \item 给定一个升序排列的整数数组$nums$，$nums$会经过如下的变化，然后作为输入
    \begin{itemize}
        \item 选择一个数组中的元素，索引是$k$
        \item 将数组中所有索引小于$k$的元素都放置到数组的尾部，例如：$nums=[0,1,2,3,4,5]$，$k=3$，则变换后的数组$nums=[3,4,5,0,1,2]$
    \end{itemize}
    \item 问题是给定一个经过上面变换的数组$nums$和一个整数$target$，问在$nums$里是否存在$target$，如果存在返回$target$对应的索引$k$，即$nums[k] = target$；如果不存在返回“-1”
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 首先这就是一个搜索题，遍历肯定是能够解决的，时间复杂度是$O(n)$。在有序数组里搜索可以用二分法，但是本题的数组整体上不是有序的，但是是有两个升序排列的数组组成，这样的数组是否可以用二分法呢？答案是可以的
    \item 二分法
    \begin{itemize}
        \item 二分法只在单调序列上有效，所以需要判断mid将数组一分为二后，哪部分是单调的
        \item 如果$nums[0]<=nums[mid]$，则说明$nums[0..mid]$是升序排列的，如果target在这区间内，就在这个区间使用二分法
        \item 如果$nums[0]>nums[mid]$，则说明$nums[0..mid]$是两段的，但是nums[mid..right]是单调升序的，如果target在这个区间，就在这个区间可以使用二分法
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]
        if target == mid_value:
            return mid
        if nums[0] <= mid_value:
            if nums[0] <= target <= mid_value:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if mid_value <= target <= nums[len(nums) - 1]:
                left = mid + 1
            else:
                right = mid - 1

    return -1
\end{lstlisting}

\section{2021-07-11}
% template - 题解
\subsection{274 H-Index}
\begin{itemize}
    \item 难度：中等
    \item 题意分析：给定一个整数数组citations用来代表一个科研人员所有文章的被引用次数, 一个元素代表一篇文章被应用的次数。如果，对于数组里的h篇文章，他们的引用次数都大于等于h，引用数为h，问题是求最大的h。
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 如果文章引用数的数组是从小到大排列，那么n就应该满足$citations[i] \ge length(citations) - i$，其中$0 \le i \le length(citations))$，这时$h = length(citations) - i$。
    \item 步骤
    \begin{enumerate}
        \item 将citations数组排序，由小到大排列
        \item 后序遍历数组，按照h满足的条件关系，进行判断就可以。因为是从大向小变化，所以最后满足条件的h为最大值
    \end{enumerate}
\end{itemize}


\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def hIndex(self, citations: List[int]) -> int:
    citations = sorted(citations)
    count = len(citations)

    h = 0
    for i in range(count - 1, -1, -1):
        if citations[i] >= count - i:
            h = count - i

    return h
\end{lstlisting}

\section{2021-07-17}

% template - 题解
\subsection{Offer 42. 求连续子数组的最大值}
\begin{itemize}
    \item 难度：中等
    \item 题意分析:
    \begin{itemize}
        \item 求数组$nums$的连续子数组的和可以通过前缀和的方法来求解。此题就转换为先求前缀和，然后通过前缀和求出所有子数组的和，最后得出最大值。时间复杂度分析：求所有前缀和的值$presums$是$O(n)$，求出所有子数组的和是$O(n^2)$，因为要遍历所有的$presums[j] - presums[i] (length(nums) \ge j > i)$。整体的时间复杂度是$O(n^2)$。当$nums$的长度大于$10^5$时，会大概率超时。
        \item 能否考虑其他的方法来求解？尝试用动态规划来求解。动态规划求解的思路就是问题可以转化为子问题的求解。假设$dp[i]$表示以$nums[i]$结尾的子数组和的最大值。$nums$的所有子数组的最大值就是$dp$数组元素的最大值。状态转移方程
        $$
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        $$
        当考虑nums[i]时，会有两种可能性:1) nums[i]单独为一个子数组; 2) nums[i]和之前的元素组成新的子数组，取两种情况的最大值就是$dp[i]$。
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 一维dp数组
    \item 初始化：$dp[0] = nums[0]$
    \item 状态转移方程：$dp[i] = max(dp[i-1] + nums[i], nums[i])$
    \item 问题的解就是$max(dp)$
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def maxSubArray(self, nums: List[int]) -> int:
    dp = [0 for i in range(len(nums))]
    dp[0] = nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1] + nums[i], nums[i])

    return max(dp)
\end{lstlisting}


\subsection{0152 乘积最大子数组}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：给出一个整形的数组，要求返回数组中子数组的元素乘积中的最大值。从题意看类似Offer 42题，需要注意的是：
    \begin{itemize}
        \item 乘积会有负负得正的情况，需要保存最小值，在推导最大值时，要判断$nums[i]$和最小值的乘积会不会成为最大值
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
可以参考Offer 42题的解题思路，增加跟踪最小值的数组。

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def maxProduct(self, nums: List[int]) -> int:
    nums_len = len(nums)
    if nums_len == 1:
        return nums[0]

    mins = [0 for _ in range(nums_len)]
    maxs = [0 for _ in range(nums_len)]

    mins[0] = nums[0]
    maxs[0] = nums[0]
    for i in range(1, nums_len):
        mins[i] = min(nums[i], min(mins[i-1] * nums[i], maxs[i-1] * nums[i]))
        maxs[i] = max(nums[i], max(mins[i-1] * nums[i], maxs[i-1] * nums[i]))

    return max(maxs)
\end{lstlisting}

\section{2021-07-24}
休息了几天，项目太忙了，天天地Review bug、讨论需求的变更、新增加的需求。
% template - 题解
\subsection{1736. Latest Time by Replacing Hidden Digits}
\begin{itemize}
    \item 难度：简单
	\item 题意分析：给一个字符串，格式是“HH:MM”（小时:分钟），时间字符串的范围是00:00到23:59，包含00:00和23:59，字符串中的数字会被“？”所覆盖，题目要求返回将“
    ？”替换为数字后，最晚的时间
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 时间格式是24小时制，最晚的时间就是在合理的条件下，每位上的数字上取最大值
    \item 从左往右判断字符串的字符，根据下面的规则进行替换
    \item 小时的十位数如果为‘？’
    \begin{itemize}
    \item 当小时的个位数为‘0’到‘3’时，十位数最大可以是‘2’
    \item 当小时的个位数为‘4’到‘9’时，十位数最大可以是‘1’
    \item 当小时的个位数为‘？’时，十位数最大是‘2’
    \end{itemize}
    \item 小时的个位数如果为‘？’
    \begin{itemize}
        \item 当小时的十位数为‘0’和‘1’时，个位数最大可以是‘9’
        \item 当小时的十位数为‘2’时，个位数最大可以是‘3’
    \end{itemize}
    \item 分钟的十位数如果为‘？’，则分钟的十位数最大可以是‘5’
    \item 分钟的个位数如果为‘？’，则分钟的个位数最大可以是‘9’
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def maximumTime(self, time: str) -> str:
    ans = list(time)
    if ans[0] == '?':
        if ans[1] != '?':
            if int(ans[1]) <= 3:
                ans[0] = '2'
            else:
                ans[0] = '1'
        else:
            ans[0] = '2'

    if ans[1] == '?':
        if ans[0] == '2':
            ans[1] = '3'
        else:
            ans[1] = '9'

    if ans[3] == '?':
        ans[3] = '5'

    if ans[4] == '?':
        ans[4] = '9'

    return ''.join(ans)
\end{lstlisting}


\subsection{34. Find First and Last Position of Element in Sorted Array}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个升序排列的整数数组$nums$，其中包含重复的元素
        \item 给定一个整数$target$，如果$target$存在，就返回一个数组[start, end], $start$和$end$为$target$在$nums$中的起始和结束的索引，如果不存在返回[-1, -1]
        \item 要求实现一个$O(\log(n))$
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 从题意可知这是一道搜索提，数组又是有序的，只是存在重复元素。要求时间复杂度是$O(\log(n))$，那就是用二分法来求解了
    \item 用二分法查找数组是否存在$target$
    \item 如果存在
    \begin{itemize}
        \item 用二分法查找小于target的最大值的索引$left$，$left+1$就是$start$
        \item 用二分法查找大于target的最小值的索引$right$，$right-1$就是$end$
    \end{itemize}
    \item 如果不存在，返回[-1, -1]
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def searchRange(self, nums: List[int], target: int) -> List[int]:
    def binary_search(nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            mid_value = nums[mid]

            if target == mid_value:
                return mid
            elif target < mid_value:
                right = mid - 1
            else:
                left = mid + 1

        return -1

    def binary_search_left(nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            mid_value = nums[mid]

            if target == mid_value:
                right = mid - 1
            elif target < mid_value:
                right = mid - 1
            else:
                left = mid + 1

        return left - 1

    def binary_search_right(nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            mid_value = nums[mid]

            if target == mid_value:
                left = mid + 1
            elif target < mid_value:
                right = mid - 1
            else:
                left = mid + 1

        return left

    if len(nums) == 0:
        return [-1, -1]

    index = binary_search(nums, target)
    if index == -1:
        return [-1, -1]
    else:
        left = binary_search_left(nums, target)
        right = binary_search_right(nums, target)
        return [left + 1, right - 1]
\end{lstlisting}

\section{2021-07-25}

% template - 题解
\subsection{1743. Restore the Array From Adjacent Pairs}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个二维数组$Pairs[n][2]$，每行的元素代表一个整形数组里相邻的两个元素$Pair=(number1, number2)$，$number1$和$number2$只是相邻，没有前后关系，并且$Pair$在$Pairs$出现的顺序是不固定的
        \item 要求通过$Pairs$还原原来的数组$nums$
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 数组里元素的相邻元素有两种情况，头尾元素只有一个相邻元素，中间的元素有2个相邻元素
    \item 如果知道某个元素的值，要获得相邻元素，就需要查询，通过HashMap可以来优化查询。通过遍历$Pairs$数组就可以构建$PairsHashMap<key, value>$，$key$是数组里的元素，$value$是一个list，用来保存元素的相邻元素。
    \item 如何发现头元素呢？在构建$PairsHashMap$的同时，可以统计元素出现的次数，头尾元素只会出现一次，也可以用$CountHashMap<key, value>$来完成，$key$是数组里的元素，$value$是元素出现的个数。
    \item 构建好$PairsHashMap$和$CountHashMap$后，通过遍历$CountHashMap$里找到第一个$value$是1的key，对应的$key$就是头元素。
    \item 然后通过当前元素去$PairsHashMap$里查找相邻元素，除了头元素外，其他的元素都会得到2个值，这两个值有一个已经在当前元素的前一个，另外一个就是下一个元素。
    假设现在求第i个元素:
    \begin{itemize}
        \item 查询元素$nums[i-1]$的相邻元素，$Values = PairsHashMap[nums[i-1]]$,$Values$为$[value1, value2]$
        \item $nums[i]$等于$value1$和$value2$中的一个，只要这个数不等于$nums[i-2]$
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
    cnt_dict = defaultdict(int)
    item_dict = defaultdict(list)

    for a, b in adjacentPairs:
        cnt_dict[a] += 1
        cnt_dict[b] += 1
        item_dict[a].append(b)
        item_dict[b].append(a)

    start = 0
    for key, value in cnt_dict.items():
        if value == 1:
            start = key
            break

    nums_len = len(adjacentPairs) + 1
    ans = [0] * nums_len
    ans[0] = start
    ans[1] = item_dict[start][0]

    for i in range(2, nums_len):
        values = item_dict[ans[i-1]]
        for value in values:
            if value != ans[i-2]:
                ans[i] = value

    return ans
\end{lstlisting}

\subsection{36. Valid Sudoku}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：用一个二维数组来表示一个9x9的数独，‘.’代表没有填数字。判断一个9x9的数独是否有效，True代表有效，False代表无效。
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 有3个标准，每行的数字不能重复，每列的数字不能重复，每个3x3的格子里数字不能重复
    \item 判断是否重复出现，可以用Hashmap来优化查询，那么就需要为每行，每列，每个3x3的格子生成Hashmap。Hashmap的key是数字，value是出现的次数。利用defaultdict(int)能够方便地处理默认值
    \item 遍历9x9的每个格子cell，更新格子在行，列，3x3格子的出现次数（hashmap的操作）。更新完成后，检查cell出现的次数是否大于1，如果大于1，就返回无效False，如果遍历结束，返回有效True
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [defaultdict(int) for _ in range(9)]
    cols = [defaultdict(int) for _ in range(9)]
    boxes = [defaultdict(int) for _ in range(9)]

    for i in range(9):
        row = rows[i]
        for j in range(9):
            col = cols[j]
            cell = board[i][j]

            if cell != '.':
                row[cell] = row[cell] + 1
                if row[cell] > 1:
                    return False

                col[cell] = col[cell] + 1
                if col[cell] > 1:
                    return False
                box_id = (i // 3) * 3 + j // 3
                box = boxes[box_id]
                box[cell] = box[cell] + 1
                if box[cell] > 1:
                    return False

    return True
\end{lstlisting}


\section{2021-08-01}

% template - 题解
\subsection{1337. The K Weakest Rows in a Matrix}
\begin{itemize}
    \item 难度：简单
	\item 题意分析：
    \begin{itemize}
        \item 给一个$m \times n$的矩阵$matrix$，矩阵中的每一行都由1和0组成，1代表军人，0代表平民，1总是排在0的左边。
        \item 需要比较每行的强弱，强弱的比较是通过比较每行的军人数量，数量少的就弱，如果军人数相等，那么行号小的弱
        \item 问题要求返回一个数组，元素是$K$个最弱的行的索引
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 需要遍历每行，得到每行的军人数。要得到每行军人的数量，最简单的做法就是从左往右遍历每行的元素，第一个0的索引就是军人的数量,时间复杂度是$O(n)$。如果考虑到每行元素是有序排列，查找最右边1的索引就可以得到军人的数量，二分查找法是可以做到的
    \item 对[军人数, 行号]这个数据对进行排序，可以采用Python已经支持的排序算法。也可以利用Python的heapq实现的小根堆，来保存[军人数, 行号]数据对，然后依次弹出需要的$K$个元素。因为有m行，所以数据量是m，单调栈的时间复杂度是$O(m)$
    \item 将前$K$个数据对的行号放入数组返回即可
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
    def binary_search_right(nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            mid_value = nums[mid]

            if target == mid_value:
                left = mid + 1
            elif target > mid_value:
                right = mid - 1
            else:
                left = mid + 1

        return left

    # 利用heapq创建一个小根堆
    h = []

    # 遍历矩阵，利用二分法来得到军人数量
    for i in range(len(mat)):
        row = mat[i]
        solder_count = binary_search_right(row, 1)
        heapq.heappush(h, (solder_count, i))

    count = k
    ans = []
    while count > 0:
        solder_count, row = heapq.heappop(h)
        ans.append(row)
        count -= 1

    return ans
\end{lstlisting}


\section{2021-08-07}

% template - 题解
\subsection{457. Circular Array Loop}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个数组$nums$，$nums[i]$的值表示索引i的元素应该移动的步数，假设$nums[i]=n$
        \begin{itemize}
            \item 如果$n$是正数，则向前移动$n$步
            \item 如果$n$是负数，则向后移动$n$步
        \end{itemize}
        \item $nums$是一个环形数组，最后一个元素向前移动一步就会达到第一个元素，第一个元素向后移动一步就到达最后一个元素
        \item 如果$nums$里存在子序列$seq$，并且按照规则能够满足$seq[0]->seq[1]->seq[k-1]->seq[0]$，则$seq$为一个循环，循环的长度为$k$
        \begin{itemize}
            \item k > 1
            \item $nums[seq[i]]$的值都是整数或者都是负数
        \end{itemize}
        \item 题目要求是判断$nums$是否存在循环，如果存在，返回True，否则，返回False
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 如果把$nums$想象为一个循环链表，判断循环链表中是否有环，可以用快慢指针的算法来解
    \item 此题给出的环形数组，其实是一个图，图中的每个节点都有一条出边，此题转化为图论里是否存在环的问题
    \item 此题可以用模拟的方法来解
    \begin{itemize}
        \item 从数组中的每一个元素出发，按照规则依次遍历$nums$，元素在循环里，在遍历过程中会再次碰到出发的元素，这时判断k的值就可以。如果元素不在循环里，但是从该元素出发会进入一个循环，则会出现k的值不断增长，当k值大于$nums$的长度时，说明出发元素不可能存在于循环里，返回False
        \item 因为Python支持索引为负值，这里不需要将负值的索引转换为正值
        \item 如果$nums[i]$的值为0，即一个元素的自循环，根据题意k=1，返回false
        \item 时间复杂度：遍历每个元素的时间复杂度为$O(n)$；从每个元素出发，判断是否存在循环的时间复杂度为$O(n)$，整体的时间复杂度为$O(n^2)$
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{itemize}
    \item 快慢指针的解法（Leetcode官方解法）
    \begin{lstlisting}[language=python]
def circularArrayLoop(self, nums: List[int]) -> bool:
    fast_pointer = 0
    slow_pointer = 0

    nums_count = len(nums)

    def next(cur:int) -> int:
        return (cur + nums[cur]) % nums_count  # 保证返回值在 [0,n) 中

    for i, num in enumerate(nums):
        if num == 0:
            continue
        slow_pointer = i
        fast_pointer = next(i)

        # 判断同号，因为fast要走两步，所以要比较slow和fast，以及slow和next（fast)
        while nums[slow_pointer] * nums[fast_pointer] > 0 and nums[slow_pointer] * nums[next(fast_pointer)] > 0:
            if slow_pointer == fast_pointer:
                if slow_pointer == next(fast_pointer):
                    break
                return True

            slow_pointer = next(slow_pointer)
            fast_pointer = next(next(fast_pointer))

        # 将从i开始、所有满足条件的nums设置为0，避免再次探测
        add = i
        while nums[add] * nums[next(add)] > 0:
            tmp = add
            add = next(tmp)
            nums[add] = 0

    return False
    \end{lstlisting}
    \item 模拟解法
    \begin{lstlisting}[language=python]
def circularArrayLoop_simulate(self, nums: List[int]) -> bool:
    # 返回是否cur为循环的开始节点
    def check(cur: int) -> bool:
        k = 1
        start_gt_zero = nums[cur] > 0
        start = cur
        if nums[cur] == 0:
            return False

        while True:
            if k > nums_count:
                return False

            next_index = (cur + nums[cur]) % nums_count
            if start_gt_zero and nums[next_index] < 0:
                return False
            if not start_gt_zero and nums[next_index] > 0:
                return False
            if start == next_index:
                return k > 1

            cur = next_index
            k += 1

    nums_count = len(nums)
    for i in range(nums_count):
        if check(i):
            return True

    return False
    \end{lstlisting}
\end{itemize}

\section{2021-08-14}

% template - 题解
\subsection{1583. Count Unhappy Friends}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给出两个列表$preferences$和$pairs$
        \item $preferences[i]$是一个整数数组，代表朋友i与其他朋友的亲密程度，朋友的排列按照亲密程度是由高到低排序。朋友共有n位，n总是偶数，朋友按照0到n-1编号
        \item $pairs$是一个朋对的列表，$pairs[i]=[x_i, y_i]$表示$x_i$和$y_i$互相配对
        \item 这样的配对关系，对使朋友不愉快。假设x和y配对，u和v配对，在满足下面的条件时，x会不愉快
        \begin{itemize}
            \item x与u的亲密程度超过x与y的亲密程度
            \item u与x的亲密程度超过u与v的亲密程度
        \end{itemize}
        \item 问题是在给定$preferences$和$pairs$的情况下，返回不愉快的朋友数量
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
好像没有特别合适的算法，所以就尝试用模拟法来解决。在模拟的过程中，存在查询搜索的操作，需要优化。
\begin{itemize}
    \item 遍历所有的朋友$x$，找到与$x$配对的$y$，需要实现查找与$x$配对的朋友，通过Hashmap预处理$pairs$，形成朋友的配对信息$HashMap<int, list<int>>$来优化查询，key为朋友索引，value为可以配对的朋友列表
    \item 用$Q_x[y]$表示朋友$y$在$x$的亲密度，值为$y$在$x$的亲密度数组的索引值，索引值越小的亲密度越大。如果存在满足不愉快条件的朋友$u$，则存在$Q_x[u]<Q_x[y]$，这里比较亲密度会涉及查询操作，可以优化查询。另外，不需要对所有$x$的朋友，进行判断，只需要针对满足条件$Q_x[u]<Q_x[y]$的朋友进行判断即可
    \item 亲密度索引值的查询可以用二维数组$prefs[n][n]$来保存，$Q_x[y] = prefs[x][y]$，$prefs[x][x]$的值无效
    \item 因为一个朋友存在多个配对，可能多个配对都导致该朋友不愉快，但是只统计一次
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
    # 存放朋友亲密度的索引值
    prefs = [[-1] * n for _ in range(n)]
    for i in range(len(preferences)):
        pref_array = preferences[i]
        for q, friend in enumerate(pref_array):
            prefs[i][friend] = q

    # 存放配对信息
    pair_dict = defaultdict(list)
    for i, pair in enumerate(pairs):
        pair_dict[pair[0]].append(pair[1])
        pair_dict[pair[1]].append(pair[0])

    ans_dict = defaultdict(int) # 即使他有多个配对都是不愉快，一个朋友只统计一次不愉快，
    ans = 0

    for x in range(n):
        if ans_dict[x] != 0:
            continue

        x_paired_friends = pair_dict[x]
        if len(x_paired_friends) > 0:
            for _, y in enumerate(x_paired_friends):
                q_y = prefs[x][y]
                if q_y > 0:
                    for i in range(q_y):
                        u = preferences[x][i]
                        q_u_x = prefs[u][x]

                        u_paired_friends = pair_dict[u]
                        if len(u_paired_friends) > 0:
                            for v in u_paired_friends:
                                if v != x and v != y:
                                    q_u_v = prefs[u][v]
                                    if q_u_x < q_u_v:
                                        if ans_dict[x] == 0:
                                            ans_dict[x] += 1
                                            ans += 1
    return ans
\end{lstlisting}

\section{2021-08-28}

% template - 题解
\subsection{0037 Sudoku Solver}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：解决$9\ast 9$ 数组代表的数独，其中“.”代表空的格子
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 此题的基础是“36. Valid Sudoku”，此题的基础是如何来判断一个数独题是否是可解的数独。需要判断行、列、$3\ast3$的9宫格是否满足数独的要求
    \item 逐行来尝试求解，递归求解。求解方法就是回溯法
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def solveSudoku(self, board: List[List[str]]) -> None:
    # 保存每行的填充情况
    rows = [[False] * 9 for _ in range(9)]
    # 保存每列的填充情况
    cols = [[False] * 9 for _ in range(9)]
    # 保存3x3的小格子填充情况，每个小格子有9个元素
    boxes = [[[False] * 9 for _a in range(3)] for _b in range(3)]
    # 保存'.'的坐标 (row, col)
    spaces = []
    # 保存是否找到答案的标志
    found = False

    def solve_sudoku(step: int) -> bool:
        nonlocal rows, cols, boxes, spaces, found
        # 如果全部走完了，说明找到答案了
        if step == len(spaces):
            found = True
            return

        # 没有走完，尝试1到9的数字

        i, j = spaces[step]
        for cell in range(9):
            if (rows[i][cell] or cols[j][cell] or boxes[i // 3][j // 3][cell]) is False:
                rows[i][cell] = cols[j][cell] = boxes[i // 3][j // 3][cell] = True
                board[i][j] = str(cell + 1)
                solve_sudoku(step + 1)
                rows[i][cell] = cols[j][cell] = boxes[i // 3][j // 3][cell] = False

            if found:
                return

    # 初始化数独的开局
    for row in range(9):
        for col in range(9):
            cell_value = board[row][col]
            if cell_value == '.':
                # 如果是'.'，记录需要填数字的格子
                spaces.append((row, col))
            else:
                # 标记数字已经被使用了
                value = int(cell_value) - 1
                rows[row][value] = True
                cols[col][value] = True
                boxes[row // 3][col // 3][value] = True

    solve_sudoku(0)
\end{lstlisting}

\section{2021-08-29}

% template - 题解
\subsection{1588. Sum of All Odd Length Subarrays}
\begin{itemize}
    \item 难度：简单
	\item 题意分析：给定一个包含正整数的数组，要求计算所有元素个数为奇数的子数组的元素和
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 求子数组的元素和可以用前缀和的方法
    \item 遍历所有可能的子数组，如果元素个数为奇数，就累计元素和
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
    ans = 0
    array_len = len(arr)

    pre_sums = [0] * (array_len + 1)
    for i in range(array_len):
        pre_sums[i+1] = pre_sums[i] + arr[i]

    for i in range(array_len):
        for j in range(i, array_len):
            if (j - i + 1) % 2 != 0:
                ans += pre_sums[j + 1] - pre_sums[i]

    return ans
\end{lstlisting}

\section{2021-09-10}

% template - 题解
\subsection{1894. Find the Student that Will Replace the Chalk}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个包含非负整数的数组$chalk$，索引$i$对应数字对于$chalk[i]=n$的含义是编号$i$的学生会使用$n$根粉笔
        \item 给定已有的粉笔数$target$，让学生依次（编号从0开始，逐渐增加，不断循环）开始使用粉笔，当剩余粉笔数小于学生会使用的粉笔数时，这位学生就需要补充粉笔
        \item 问题是：在给定$chalk$和$target$时，求出需要补充粉笔的学生编号
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 采用模拟法就可以求解
    \item 因为粉笔是循环使用，$target$除$chalk$元素的和的余数就是最后一轮剩余的粉笔数
    \item 针对最后一轮剩余的粉笔数，再次模拟使用粉笔，判断剩余的粉笔是否满足学生的粉笔使用量，就可以求得需要补充粉笔的学生编号
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def chalkReplacer(self, chalk: List[int], k: int) -> int:
    total_chalk_count = sum(chalk)
    last_loop_chalk = k % total_chalk_count

    for i in range(len(chalk)):
        if last_loop_chalk < chalk[i]:
            return i
        else:
            last_loop_chalk -= chalk[i]

    return 0
\end{lstlisting}


\section{2021-09-11}

% template - 题解
\subsection{0600. Non-negative Integers Without Consecutive Ones}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 给定一个正整数，要求求出小于或者等于正整数的非负数中，其二进制中不包含连续1的数的个数。正整数的数值范围:$1<n<10^9$
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 从数值范围来判断，用模拟法直接遍历会超时，需要寻找其他方法
    \item 首先分析一下不连续$1$出现的情况，按照二进制数的为数从小考虑
    \begin{itemize}
        \item 1位，{0,1}，结果是2
        \item 2位，{00, 01, 10, 11}，结果是3
        \item 3位，{000, 001, 010, 011}和{100, 101, 110, 111}，结果是$3+2=5$。从2位变为3位，其实就是在最前面添加$1$和$0$
        \begin{itemize}
            \item 添加$0$，不改变原来的不连续1的数量
            \item 添加$1$，如果紧挨着的数字是$1$，则为连续的$1$，无效的情况；如果紧挨着的数字是$0$，则不连续$1$的情况就是整个位数减去2（添加了1和紧挨着是0，所以是2）的情况
        \end{itemize}
    \item 所以可以推出$n$位二进制数，不连续$1$的情况为$n-1$（前面添加$0$）的情况加上$n-2$（前面添加$1$）的情况，其实就是斐波拉契数列
    \end{itemize}
    \item 上面已经求出$n$位二进制数的情况了，如何求一个具体的数呢？可以拆分区段
    \item 举例说明：$10101$
    \begin{itemize}
        \item $0000$ - $1111$，其实是$0000$ - $1111$，考虑4位
        \item $10000$ - $10011$，其实是$00$ - $11$，考虑2位
        \item ......
        \item 如果给定的二进制数里包含连续的$1$，则后续的区段不再考虑
        \item 如果给定的没有包含连续的$1$，则最后再加1
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def findIntegers(self, n: int) -> int:
    def get_binary_str(n: int) -> str:
        return bin(n)[2:]

    dp = [0] * 32
    dp[0] = 1
    dp[1] = 2

    for i in range(2, 32):
        dp[i] = dp[i - 1] + dp[i - 2]

    bin_str = get_binary_str(n)

    ans = 0

    for i in range(len(bin_str)):
        if bin_str[i] == '0':
            continue
        ans += dp[len(bin_str) - i - 1]
        if i != 0 and bin_str[i - 1] == '1':
            return ans

    ans += 1
    return ans
\end{lstlisting}


\section{2021-09-12}

% template - 题解
\subsection{67. Valid Parenthesis String}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给出一个字符串，字符串由“（”，“）”，“*“三种符号组成，要求判断字符串是否有效
        \item 有效的定义是：左括号必须和右括号配对，”*“可以是左括号，右括号和空字符的其中一种
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 判断字符串中的括号是否有效，其实就是判断左右括号是可以配对，可以用栈来实现。本题多了一个星号，使得要考虑的case多了
    \item 栈的解法
    \begin{itemize}
        \item 因为有星号，所以需要两个栈，一个保存左括号，一个保存星号
        \item 依次遍历字符串，将左括号和星号压栈
        \item 碰到右括号，优先从使用左括号栈来完成匹配，如果左括号栈是空的，则用星号栈来匹配，如果都空，则说明字符串无效
        \item 当字符串遍历完后，有可能出现左括号栈和星号栈不为空的情况
        \begin{itemize}
            \item 只有星号栈不为空，因为星号可以是空字符，所以字符串有效
            \item 只有左括号栈不为空，因为匹配的原则是左括号优先，所以字符串无效
            \item 如果左括号栈和星号栈都不为空，就说明需要将星号理解为右括号来使用。当星号在左括号的右侧，则星号可以和左括号匹配，反之不行。根据这个原则，依次将左括号栈的元素出栈和星号栈进行匹配。如果左括号栈最后为空，则字符串有效，反之，字符串无效。
        \end{itemize}
        \item 因为要比较左括号和星号的位置，所以我们需要将左括号和星号的索引进行压栈
    \end{itemize}
    \item 动态规划的解法
    \begin{itemize}
        \item 动态规划的算法框架：设计DP数组、递推公式、DP数组的初始化、如何遍历
        \item
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def checkValidString(self, s: str) -> bool:
    def check_stack(s: str) -> bool:
        left_stack = Stack()
        star_stack = Stack()

        for i, ch in enumerate(s):
            if ch == '(':
                left_stack.push(i)
            elif ch == '*':
                star_stack.push(i)
            elif ch == ')':
                if not left_stack.is_empty():
                    left_stack.pop()
                elif not star_stack.is_empty():
                    star_stack.pop()
                else:
                    return False

        left_empty = left_stack.is_empty()
        star_empty = star_stack.is_empty()

        if not star_empty and left_empty:
            return True
        elif not left_empty and star_empty:
            return False
        elif left_empty and star_empty:
            return True
        else:
            if left_stack.size() > star_stack.size():
                return False
            else:
                while not left_stack.is_empty():
                    left = left_stack.pop()
                    star = star_stack.pop()

                    if int(left) > int(star):
                        return False
                return True

    return check_stack(s)
\end{lstlisting}

\section{2021-09-19}
% template - 题解
\subsection{650. 2 Keys Keyboard}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 有一种记事本，只支持两种操作
        \begin{itemize}
            \item CopyAll（全部复制）操作，即将记事本上的全部内容都复制
            \item Paste（粘贴）操作，粘贴上一次复制的内容
        \end{itemize}
        \item 最初记事本上只有一个大写字符“A”，给定一个正整数$n$，计算只通过两种操作就能在记事本上输出$n$个“A”的最小操作次数
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 从题意可知，对于任何正整数都是可以完成的，只要第一次使用CopyAll，之后不断地进行Paste，总能完成，操作次数是$n$，且为最大值
    \item 假设通过一系列操作达到$j$个字符，然后$n=j*i$，之后就可以使用1次CopyApp操作和$i-1$次Paste操作达到$n$，因为$j$和$i$是$n$的因数，且$j$和$i$的组合可能有多个，就需要取其中的最小值。
    \item 动态规划的解法
    \begin{itemize}
        \item 假设$dp[n]$表示生成$n$个字符的最小操作次数
        \item 初始化条件有$dp[0]=0$和$dp[1]=0$
        \item 由上面的分析可知，递推公式为$dp[n]=Min(dp[j]+ i)$，其中$n=j*i$
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def minSteps(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 0

    for k in range(2, n + 1):
        min_step = k
        for j in range(1, k):
            if k % j == 0:
                min_step = min(min_step, dp[j] + k // j)

        dp[k] = min_step

    return dp[n]
\end{lstlisting}

\section{2021-09-20}

% template - 题解
\subsection{300. Longest Increasing Subsequence}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：给定一个整数数组$nums$，要求返回最长严格升序子序列的长度
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 子序列问题很容易想到可能用动态规划来解决
    \item 假设$dp[i]$数组中[0->i]的元素以第i个元素结尾的最长严格升序子序列的长度，$dp[0] = 1$
    \item 考虑第$i+1$个元素的情况
    \begin{itemize}
        \item 要将$nums[i+1]$加到[0->i]中所有可能的子序列的后面，如果满足严格升序，那么对应的子序列长度加1。假设$0<=j<i$，如果$nums[j] < nums[i+1]$，那么[0->j, i+1]的最大升序自序列的长度会加1。
        \item 那么$dp[i]=Max_{0 \leq j < i}(dp[j] + 1) 当nums[i] > nums[j]$
    \end{itemize}
    \item $nums$的最长严格升序子序列的长度就是所有dp中的最大值
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def lengthOfLIS(self, nums: List[int]) -> int:
    nums_len = len(nums)
    if nums_len == 1:
        return 1

    dp = [1] * nums_len

    for i in range(0, nums_len):
        for j in range(0, i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)
\end{lstlisting}

\subsection{673. Number of Longest Increasing Subsequence}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 对于给定的整数数组$nums$，求出最长严格升序子序列的序列数。
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 最长升序子序列的长度可以参考300题，现在的问题就是如何记录具有相同长度的最长子序列的个数，就需要额外的数组$gp[i]$来记录以第$i$个元素结尾的最长子序列的个数，可以看出也是动态规划的解法
    \begin{itemize}
        \item 考虑初始值，最短的子序列是只包含第$i$个元素的子序列，所以初始化为1
        \item 递推过程，当$nums[i] > nums[j]$时，这时会形成新的子序列，最大子序列长度有可能发生变化
        \begin {itemize}
            \item 长度不变，数量增加，$gp[i]$需要加上新出现的序列数$gp[j] + 1$
            \item 长度增加，$gp[i]$需要替换，$gp[i] = gp[j] + 1$
        \end{itemize}
        \item 整个递推过程结束后，求$max(dp)$可以得到最长子序列的长度，因为最长子序列可以出现在以任意元素结尾的子序列中，所以需要遍历$dp$数组，如果$dp[i]$等于最长子序列的长度，就需要统计对应的$gp[i]$，最终将得到最长子序列的个数
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def findNumberOfLIS(self, nums: List[int]) -> int:
    nums_len = len(nums)
    if nums_len == 1:
        return 1

    dp = [1] * nums_len
    gp = [1] * nums_len

    for i in range(0, nums_len):
        for j in range(0, i):
            if nums[i] > nums[j]:
                if dp[i] == dp[j] + 1:
                    gp[i] += gp[j]
                elif dp[i] < dp[j] + 1:
                    gp[i] = gp[j]
                    dp[i] = dp[j] + 1

    max_length = max(dp)

    ans = 0
    for i in range(nums_len):
        if dp[i] == max_length:
            ans += gp[i]

    return ans
\end{lstlisting}
% template - 刷题日志 - end

% template - 刷题日志 - begin
\section{2021-09-29}

% template - 题解
\subsection{517.Super Washing Machines}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 假设有$n$台洗衣机，每台洗衣机里有若干的衣服
        \item 每次可以选择其中的$m$台，选择后，每台洗衣机都会将自己的一件衣服送到相邻的一台洗衣机里
        \item 给定一个数组$machines$，里面的整数表示对应的洗衣机里有的衣服件数，要求给出让所有的洗衣机里的衣服都相等的最小操作步数，如果无法使所有洗衣机里的衣服都相等，则返回-1
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 首先，判断是否有解。最后每个洗衣机里的衣服数为衣服总数除以洗衣机的数量，如果能整除，则有解，如果不能整除则无解
    \item 在判断是否有解的过程中，已经求出了最终要达到的每个洗衣机里的衣服数$avg\_count$
    \item 每台洗衣机，每次只能将一件衣服送到相邻的一台洗衣机，或者向左或者向右传送衣服
    \item 第$i$个洗衣机的左边的洗衣机$[0...i)$，右边的洗衣机为$(i...n-1]$
    \begin{itemize}
        \item $l\_sum$表示左边洗衣机衣服的总和，$a=avg\_count \times (i) - l\_sum$表示需要从右边移入的衣服数，大于0时有意义
        \item $r\_sum$表示右边洗衣机衣服的总和，$b=avg\_count \times (n-1-i) - r\_sum$表示需要向左边移出的衣服数，大于0时有意义
    \end{itemize}
    \item 每次操作只能移动一件衣服，所以移动的衣服数就是操作步骤数
    \item 对于每个洗衣机，a + b的最大值就是第$i$个洗衣机的最小操作步骤，所有洗衣机操作步骤的最大值就是达到全部平均的最小值
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def findMinMoves(self, machines: List[int]) -> int:
    count = len(machines)
    total = sum(machines)

    if total % count > 0:
        return -1
    else:
        avg_count = total // count
        presum = 0
        ans = 0
        l_sum  = 0
        r_sum = total

        for i in range(count):
            a = max((i * avg_count - l_sum), 0)
            r_sum -= machines[i]
            b = max(((count-i-1) * avg_count - r_sum), 0)
            ans = max(ans, a+b)
            l_sum += machines[i]
        return ans
\end{lstlisting}
% template - 刷题日志 - end

% template - 刷题日志 - begin
\section{2021-10-03}

% template - 题解
\subsection{166. Fraction to Recurring Decimal}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给出两个整数，代表分子numerator和分母denominator，要求以字符串的形式返回小数
        \item 如果小数部分有循环部分，将循环部分放到括号里
        \item 整数的取值范围是32位整数
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 用长除法来模拟求小数部分即可
    \item 先求出商的整数部分，如果没有余数直接返回结果，如果有余数，小数部分会出现两种情况
    \begin{itemize}
        \item 有限不循环
        \item 有限循环部分
        \item 通过长除法可以不断求出小数部分，如果长除的过程中，出现重复出现的余数，
        说明碰到了循环部分。通过Hash表来保存余数出现所对应的小数位数，就可以得到循环节的长度，从而添加括号了
    \end{itemize}
    \item 还需要处理符号的问题，先判断除数和被除数是否异号，明确结果的符号后，将除数和被除数转为正数，再进行
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
    negative = True if numerator * denominator <0 else False
    numerator = abs(numerator)
    denominator = abs(denominator)

    quotient = numerator // denominator
    reminder = numerator % denominator

    fraction = []

    ans = []
    if negative:
        ans.append("-")

    ans.append(str(quotient))

    if reminder != 0:
        ans.append('.')
        '''
        用dict来保存余数和对应的index
        '''

        reminder_dict = {}
        fraction_index = 0
        start_index = -1
        end_index = -1
        fraction = []
        while reminder > 0:
            if reminder_dict.get(reminder, -1) != -1: # 发现重复出现的余数
                start_index = reminder_dict[reminder]
                end_index = fraction_index
                break
            else:
                reminder_dict[reminder] = fraction_index
                fraction_number = (reminder * 10) // denominator
                reminder = (reminder * 10) % denominator
                fraction_index += 1
                fraction.append(str(fraction_number))

        if start_index != -1 and end_index != -1:
            fraction.insert(start_index, "(")
            fraction.insert(end_index + 1, ")")

    return "".join(ans) + "".join(fraction)
\end{lstlisting}
% template - 刷题日志 - end

% template - 刷题日志 - begin
\section{2021-10-16}

% template - 题解
\subsection{282. Expression And Operators}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 给定一个只包含数字的字符串$num$和一个整数$target$，要求在字符串里通过添加"-","+","$\times$"符号，将字符串改造为一个数学表达式，并且运算的结果等于$target$
        \item 请给出所有满足条件的数学表达式
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 假设$num$的长度为$n$，要拼接成表达式，则需要进行$n-1$选择，选择的范围是["", "-", "+", "$\times$"]，选择不填运算符有个条件就是数字不能是以“0”开头的
    \item 基本思路就是将所有的拼接表达式都求出来，并且进行求值，当和$target$相等时，记录表达式，很明显是用回溯法来求解。
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def addOperators(self, num: str, target: int) -> List[str]:
    n = len(num)
    ans = []

    def backtrack(expr: List[str], i: int, res: int, mul: int):
        if i == n:
            if res == target:
                ans.append(''.join(expr))
            return
        signIndex = len(expr)
        if i > 0:
            expr.append('')  # 占位，下面填充符号
        val = 0
        for j in range(i, n):  # 枚举截取的数字长度（取多少位）
            if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零
                break
            val = val * 10 + int(num[j])
            expr.append(num[j])
            if i == 0:  # 表达式开头不能添加符号
                backtrack(expr, j + 1, val, val)
            else:  # 枚举符号
                expr[signIndex] = '+';
                backtrack(expr, j + 1, res + val, val)
                expr[signIndex] = '-';
                backtrack(expr, j + 1, res - val, -val)
                expr[signIndex] = '*';
                backtrack(expr, j + 1, res - mul + mul * val, mul * val)
        del expr[signIndex:]

    backtrack([], 0, 0, 0)
    return ans
\end{lstlisting}
% template - 刷题日志 - end

%----------------------------------------------
\section{2021-12-05}
% template - 题解
\subsection{2092. Find All People With Secret}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 有n个专家，然后给定一个数组$meetings$，数组$meetings$的每个元素是个包含3个元素的子数组$subarray$。$subarray[0]$和$subarray[1]$表示参加会议的专家ID，$subarray[2]$表示会议ID
        \item 在同一轮会议中，所有的会议是同时举行的，一个专家获得的信息会传递和他开会的专家
        \item 专家0，专家target会先开会，这样专家0和专家target都分享一个秘密，然后专家会按照$meetings$提供的信息，按照会议id从小到大进行开会
        \item 会议结束后，请返回知道这个密码的专家ID
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 采用归并集的方法来实现
    \item 每次会议进行一次归并操作，然后将根元素不是0的元素的根元素恢复为它自己
    \item 最后，遍历整个数组，将根元素是0的元素，添加到list里，返回即可
\end{itemize}

\subsubsection{解题代码 - 在leetcode上会超时}
\begin{lstlisting}[language=python]
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
    def find(x):
        nonlocal fa, rank
        if fa[x] == x:
            return fa[x]
        else:
            fa[x] = find(fa[x])
            return fa[x]

    def merge(i, j):
        nonlocal fa, rank
        x = find(i)
        y = find(j)

        if rank[x] <= rank[y]:
            fa[x] = y
        else:
            fa[y] = x

        if rank[x] == rank[y] and x != y:
            rank[y] += 1

    meeting_map = {}

    for item in meetings:
        if not meeting_map.get(item[2]):
            meeting_map[item[2]] = [[item[0], item[1]]]
        else:
            meeting_map[item[2]].append([item[0], item[1]])

    fa = [0] * n
    rank = [1] * n

    for i in range(n):
        fa[i] = i

    merge(firstPerson, 0)

    for meeting_time in sorted(meeting_map):
        persons = meeting_map.get(meeting_time)
        for meeting_pair in persons:
            merge(meeting_pair[0], meeting_pair[1])

        root = find(0)
        for i in range(1, n):
            if find(i) != root:
                fa[i] = i

    ans = [0]
    root = find(0)
    for i in range(1, n):
        if find(i) == root:
            ans.append(i)

    return ans
\end{lstlisting}
\subsubsection{解题代码 - leetcode Pass}
\begin{lstlisting}[language=python]
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
    def find(x):
        nonlocal fa, rank
        if fa[x] == x:
            return fa[x]
        else:
            fa[x] = find(fa[x])
            return fa[x]

    def merge(i, j):
        nonlocal fa, rank
        x = find(i)
        y = find(j)

        if rank[x] <= rank[y]:
            fa[x] = y
        else:
            fa[y] = x

        if rank[x] == rank[y] and x != y:
            rank[y] += 1

    meetings.sort(key=lambda x: x[2])

    fa = [0] * n
    rank = [1] * n

    for i in range(n):
        fa[i] = i

    merge(firstPerson, 0)
    meeting_len = len(meetings)

    index = 0
    while index < meeting_len:
        j = index
        while j + 1 < meeting_len and meetings[j + 1][2] == meetings[index][2]:
            j += 1

        for i in range(index, j + 1):
            merge(meetings[i][0], meetings[i][1])

        root = find(0)
        for i in range(index, j + 1):
            if find(meetings[i][0]) != root:
                fa[meetings[i][0]] = meetings[i][0]
                rank[meetings[i][0]] = 1
            if find(meetings[i][1]) != root:
                fa[meetings[i][1]] = meetings[i][1]
                rank[meetings[i][1]] = 1

        index = j + 1

    ans = [0]
    root = find(0)
    for i in range(1, n):
        if find(i) == root:
            ans.append(i)

    return ans
\end{lstlisting}
代码优化的地方
\begin{itemize}
    \item 去掉将meetings转化为dict的过程，直接将meetings排序
    \item 处理完每轮会议后，不是遍历所有的专家，而是只遍历参加会的专家，减少的for循环的数量
\end{itemize}

\section{2022-01-15}
\subsection{2127.Maximum Employees to Be Invited to a Meeting}
\begin{itemize}
    \item 难度：困难
    \item 一个公司准备组织一场会议，邀请名单上有$n$位员工。公司准备了一张圆形的桌子，可以坐下任意数目的员工
    \item 员工编号为0到$n-1$，每位员工都有一位喜欢的员工，每位员工当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己
    \item 给你一个下标从0开始的整数数组$favorite$，其中$favorite[i]$表示第i位员工喜欢的员工。请你返回参加会议的最多员工数目
\end{itemize}


\subsubsection{解题思路}
本题的难度是困难，主要是因为用到了比较少见的数据和对应的算法知识。

此题需要的数据结构知识：
\begin{itemize}
    \item 图以及图相关的算法：拓扑排序
    \item 基环树的概念
\end{itemize}

通过分析题意，将题意映射到基环树这个复杂数据结构上，可以把环理解为是一个根，其他的员工像是根上的枝干，然后通过进一步分析题意，根据环的长度来分类讨论，最后给出题解。
\begin{itemize}
    \item 每个员工都有一个他喜欢的员工，所以属于一个环上的员工都能参加会议。环上的员工数量大于等于2。
    \begin{itemize}
        \item 当环的数量大于等于3时，只能是换上的员工参加会议，如果加入枝干，那么会导致喜欢链接枝干的员工无法和喜欢他的员工挨着，因为位置被枝干上的员工占了，所以，当环的数量大于等于3时，只能是环上的员工参加会议
        \item 当环的数量等于2时，如果加入枝干上的员工，环上的员工仍然会和他喜欢的员工挨着，这是桌上的员工数量为2加上枝干上员工的数量。环上的2个员工的枝干是都可以做到一张桌子的，所以，这时的最大值就是环上两个员工的枝干的最大值加上2
    \end{itemize}
    \item 通过上面的分析，解题步骤就是
    \begin{itemize}
        \item 找出树中的环，如果处在大于等于3个环，保留员工数最大的值
        \item 如果环的数量为2，计算环上最大的枝干长度，加2
        \item 上面结果中取最大值就是答案
    \end{itemize}
\end{itemize}

\subsubsection{解题代码}
待补充

\section{2022-04-09}
\subsection{780. Reaching Points}
\begin{itemize}
    \item 难度：困难
    \item 给出两个正整数对 ，起始数对$(sx, sy)$和目标数对$(tx, ty)$
    \item 每次可以对数对进行如下变换中的一个变换，产生新的数对$(new\_x, new\_y)$
    \begin{itemize}
        \item $(new\_x = sx+sy, new\_y = sy)$
        \item $(new\_x = sx, new\_y = sx + sy)$
    \end{itemize}
    \item 问题是请判断经过诺干次变换后，是否可以从起始数对得到目标数对
\end{itemize}

\subsubsection{解题思路}
从题意看出，此题用递归的方法就可以解题。从起始数对开始递归，每次会产生两个新的数对，再用新数对进行递归。
每次比较新数对和目标数对，如果相等就退出递归，返回True，如果数对里的数超过目标数对说明无法得到目标数对，结束递归。

目标数对可以是一个很大的正整数，所以从起始数对开始递归，递归次数会非常多，很容易超时。正向不行，能不能反向递归，从目标数组开始，进行逆操作，看看能否得到起始数对。

目标数对的数可能有两种情况：
\begin{itemize}
    \item $tx\equiv ty$时，因为$tx$或$ty$是通过$sx + sy$变换得来的, 所以变换后的数对为$(sx + sy, sy)$ 或者$(sx, sx + sy)$，新数对的两个数不可能相等，所以目标数对中的数是相等的情况是无法达到的。
    \item $tx \neq ty$时，$tx$和$ty$中较大的数是由经过变换的数，另外一个数是上一次的数，两数相减能得到变换前数对的另一个数。
\end{itemize}

这样反向递归是不是就不会超时了呢？还是有可能的。思考一下，如果$tx$是64位的正整数的最大值，$ty$是1, 递归次数是不是会很大。这种情况下如何优化呢？这种情况下的递归，相当于大数会不断的减去小数，直到变的比另外一个数小才会停止。这个过程就相当于$bigNumber$和$smallNumber$做除法求余数。

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
    if tx < sx or ty < sy:
        return False
    if tx > ty:
        # 说明ty不会再变化了，tx只能是 n * ty + sx
        if sy == ty:
            if (tx - sx) % ty == 0:
                return True
            else:
                return False
        else:
            return self.reachingPoints(sx, sy, tx % ty, ty)
    elif tx < ty:
        # 说明tx不会再变化了，ty只能是 n * tx + sy
        if sx == tx:
            if (ty - sy) % tx == 0:
                return True
            else:
                return False
        else:
            return self.reachingPoints(sx, sy, tx, ty % tx)
    else:
        return sx == tx and sy == ty
\end{lstlisting}

\subsection{2140. Solving Questions With Brainpower}
\begin{itemize}
    \item 难度：中等
    \item 给出一个二维数组$questions[i]$，其中$questions[i]={score_i, brain_power_i}$，$score_i$表示解决第$i$个问题可以获得的分数，$brain_power_i$表示解决了此问题后，需要跳过$brain_power_i$个问题后，脑力才能恢复，才能继续解题
    \item 解题的过程中，针对每一道题可以选择解决或者跳过。解题时，脑力必须得到恢复
    \item 问题是针对给出的$questions$数组，给出最多的得分
\end{itemize}

\subsubsection{解题思路}

从题意看，针对每个题都有两种选择：做和不做，后面的得到依赖于前面做题的选择，适合采用递归或者动态规划的方法来解决。

\paragraph{递归的解法}

假设$dfs(index)$ 表示从$index$道开始做题后的最多得分。两种情况的得分是：
\begin{itemize}
    \item 如果选择做题，得分为当前题的分数：$score_index$ + 从恢复脑力后开始做题的得分$dfs(index + jump + 1)$
    \item 如果选择跳过，得分为做下一道题的分数：$dfs(index + 1)$
\end{itemize}
取两者的大值就是最后的最多得分。

\paragraph{动态规划的解法} 按照动态规划的解题步骤来
\begin{itemize}
    \item 设数组$dp[n]$，由于从任何一道题开始做题的最大得分不受之前得分的影响，所以设$dp[i]$表从索引$i$开始做题，所能得到的最多得分。
    \item 针对$i$
    \begin{itemize}
        \item 如果不做，$dp[i] = dp[i+1]$
        \item 如果做, $dp[i] = score_{index} + dp[index_{next\_jump}]$
        \item 取两种情况的大值复制到$dp[i]$
    \end{itemize}
    \item 由于从某道题开始的最大得分不受前面题的最大得分的影响，采用逆序求解
    \item $dp[0]$就是答案
\end{itemize}

\subsubsection{解题代码 - 递归解法}
\begin{lstlisting}[language=python]
def mostPoints_dfs(self, questions: List[List[int]]) -> int:
    question_count = len(questions)

    # 从cur开始的最大值
    # cache请参考：https://www.gairuo.com/p/python-function-cache
    @cache
    def dfs(cur:int) -> int:
        if cur > question_count - 1:
            return 0
        elif cur == question_count - 1:
            return questions[cur][0]
        else:
            score = questions[cur][0]
            pass_count = questions[cur][1]
            return max(score + dfs(cur + pass_count + 1), dfs(cur + 1))

    return dfs(0)
\end{lstlisting}

\subsubsection{解题代码 - 动态规划解法}


\begin{lstlisting}[language=python]
def mostPoints(self, questions: List[List[int]]) -> int:
    n = len(questions)
    dp = [0] * (n + 1)

    for i in range(n-1, -1, -1):
        point, question = questions[i]
        jump = i + question + 1
        dp[i] = max(dp[i+1], point + (dp[jump] if jump <n else 0))

    return dp[0]
\end{lstlisting}
%---------------------------------------------------------
\section{2022-04-16}
\subsection{2151. Maximum Good People Based on Statements}
\begin{itemize}
    \item 难度：困难
    \item 游戏中有两种角色:
    \begin{itemize}
        \item 好人：只说真话
        \item 坏人：可能说真话，也可能说假话
    \end{itemize}
    \item 给定一个$n \times n$的数组$statements$，描述了游戏参与者对其他人的评价，$statements[i][j]$代表编号$i$对编号$j$的评价
    \begin{itemize}
        \item $0$表示$i$认为$j$是坏人
        \item $1$表示$i$认为$j$是好人
        \item $2$表示不评价
    \end{itemize}
    \item 自己是无法评价自己的，所以$statements[i][i] = 2$
    \item 题目要求是基于$statements$，计算出最多的好人数
\end{itemize}

\subsubsection{解题思路}
从题意看，这道题的基本解题过程应该如下：
\begin{itemize}
    \item 假设某位参与是好人，然后根据$statements$数组进行分析，判断是否合理
    \item 如果合理，则之前的假设是对的，这时，好人数加$1$，否则这为参与者就是坏人。然后再处理下一位参与者是好人的情况
    \item 依次进行，最后返回好人数的最大值
\end{itemize}

从解题过程看，回溯法比较适合这类解题过程。

\subsubsection{解题代码}
\begin{lstlisting}{language=python}
class Solution(SolutionBase):
    def __init__(self):
        self.max_total = 0

    def back_track(self, statements, player, good, bad):
        # base case
        if player == len(statements):
        self.max_total = max(len(good), self.max_total)
        return

        # backtracking
        for i in range(player, len(statements)):
            # prune
            if i in bad:
                continue

            new_good = [j for j in range(len(statements[i])) if statements[i][j] == 1]
            new_good.append(i)
            new_bad = [j for j in range(len(statements[i])) if statements[i][j] == 0]

            new_good = [x for x in new_good if x not in good]
            new_bad = [x for x in new_bad if x not in bad]

            if len(set(good + new_good).intersection(set(bad + new_bad))) > 0:
                # prune
                pass
            else:
                self.back_track(statements, i + 1, good + new_good, bad + new_bad);
            if i not in bad:
                bad.append(i)

        if len(set(good).intersection(set(bad))) > 0:
            pass
        else:
            self.max_total = max(len(good), self.max_total)

        return

    # 解题的方法，命名和Leetcode的保持一致即可
    def maximumGood(self, statements: List[List[int]]) -> int:
        self.back_track(statements, 0, [],[])
        return self.max_total
\end{lstlisting}

\section{2022-05-03}
\subsection{2157. Groups of Strings}
\subsubsection{题意说明}
\begin{itemize}
    \item 难度：困难
    \item 给定一个字符串数组$Strings$，数组里的字符串都是由小写字母组成，每个字母都只出现一次
    \item 需要将字符串数组里的字符串进行分组，分成规则是关联的字符串放到一组
    \item 两个字符串$a$和$b$关联的条件
    \begin{itemize}
        \item $a$和$b$包含的字母完全相同
        \item 当$a$ 去掉一个字母，就和$b$包含的字母相同
        \item 当$a$ 添加任意一个字母，就和$b$包含的字母相同
        \item 当$a$ 用任意一个字母替换掉包含的一个字母，就和$b$包含的字母相同
    \end{itemize}
    \item 请给出$Strings$按照上面的关联规则进行分组的小组数量以及包含字符串最多的小组中字符串的数量
\end{itemize}

\subsubsection {解题思路}
\paragraph {如何判断字符串关联}
\begin {itemize}
\item 字符串只包含小写字母，并且每个字母只出现一次，那么字母串的长度最长是26。字符串内的字母不是有序的，按照关联规则直接进行字符的比较肯定是耗时的，考虑到字母只出现一次，并且整个字符串长度不超过26，可以将每个字母表示为32位整数的一位，例如：$a$ 对应第0位为1，这样一个字符串就变成一个整数$mask$
\item 通过位来判断两个字符串是否管理
\begin{itemize}
    \item 如果两个$mask$ 只有一位是不同的，那么这两个字符串可以通过添加或者删除操作变成关联，例如：$ab$:$00000000...011$和$b$: $00000000...010$
    \item 如果两个$mask$ 中位是1的数量相同，并且只有一位1所在的位是不同，那么这两个字符串可以通过替换字母来变成关联，例如：$ab$:$00000000...011$和$cb$:$00000000...110$
    \item 如果两个$mask$ 相等，这两个字符串就是关联的，例如：$ab$:$00000000...011$和$ba$:$00000000...011$
\end{itemize}
\item 这些都可以通过异或操作加上得到二进制数中包含$1$的个数来求解，如果按照这种方法，就需要对$Strings$里的字符串进行交叉检查，复杂度是$O(n^2)$，肯定超时
\item 考虑一个字符串可能的关联字符串都有哪些？最大数量为$1 + 26 + 26 + 26 \times 26 = 729$，实际数量要比729小很多。如果将$Strings$的字符串转换为$mask$，保存在字典$dict$里，通过枚举一个字符串的所有可能关联字符串是否在$dict$里，复杂度是$O(n * 729) = O(n)$ （注：字典的查找，插入，获取，删除，时间复杂度都是$O(1)$）
\item 枚举方法
\begin{itemize}
    \item 如果某一位是$0$，对这一位异或$1$, 其他位都与$0$进行异或，就相当于加了一个字母
    \item 如果某一位是$1$，对这一位异或$1$, 其他位都与$0$进行异或，就相当于去掉一个字母
    \item 如果某一位是$1$，对这一位异或$1$，在其余是0的位中，选取一位，与$1$进行异或，其他位都与$0$进行异或，就相当于替换字母
\end{itemize}
\end{itemize}

\paragraph {如何分组}
考虑到是分组问题，并且是组间是不想关的，这里用并查集的算法来求解。
\begin{itemize}
    \item 可以用字典保存每个字符串的$mask$，并且作为并查集$fa$
    \item 针对每个字符串进行枚举可能的关联字符串$LinkString$，如果$LinkString$在$fa$中，就进行merge操作
    \item 全部字符串都处理后，就完成分组里，在操作过程中，保留组数和组内字符串数量的最大值即可
\end{itemize}

\subsubsection {解题代码}
\begin{lstlisting}[language=python]
def groupStrings(self, words: List[str]) -> List[int]:
    def word_mask(w: str) -> int:
        x = 0
        for ch in w:
            x |= 1 << (ord(ch) - ord('a'))
        return x

    def find(x):
        if fa[x] == x:
            return x
        else:
            fa[x] = find(fa[x])
        return fa[x]

    def merge(i, j):
        nonlocal group_count, max_size
        if j not in fa:
            return
        x = find(i)
        y = find(j)

        if x == y:
            return

        fa[x] = y
        size[y] += size[x]
        max_size = max(max_size, size[y])
        group_count -= 1

    count_words = len(words)
    group_count = count_words
    max_size = 0
    fa = {}
    size = defaultdict(int)

    for word in words:
        mask = word_mask(word)
        fa[mask] = mask
        size[mask] += 1
        max_size = max(max_size, size[mask])
        if size[mask] > 1:
            group_count -= 1

    for x in fa:
        for i in range(26):
            merge(x, x ^ (1 << i))
            if (x >> i) & 1:
                for j in range(26):
                    if ((x >> j) & 1) == 0:
                        merge(x, x ^(1 << i) | (1 << j))

    return [group_count, max_size]
\end{lstlisting}
%--第5章-------------------------------------------------
\chapter{分类刷题}
\section{Array}
\subsection{39. Combination Sum}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个没有重复元素的正整数数组$array$和一个正整数$target$
        \item 通过使用$array$里的元素通过相加，使和为$target$，$array$中的素可以重复使用，使用的数字可以作为一个组合，如果组合里至少有一个数字的数量是不同的，则组合是不同。
        \item 求所有等于$target$的组合
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 此题要求返回所有满足条件的解，算法应该是一个穷举的过程，不断地尝试可能的组合，很明显可以利用回溯法来求解
    \item 由于地尝试所有的组合，使用的元素会先后的顺序，根据题意先后顺序不影响结果，所以需要考虑满足结果的组合要去掉重复的组合
    \item 回溯法可以参考第三章的代码框架编写
\end{itemize}

\subsubsection{解题代码 - 未优化版}
\begin{lstlisting}[language=python]
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    def try_combination(sum_now: int, list_now: List[int]):
        nonlocal ans
        if sum_now == target:
            list_now.sort()
            new_list = tuple(list_now)
            if new_list not in ans:
                ans.add(new_list)
                return

        if sum_now > target:
            return

        for i in range(0, len(candidates)):
            try_combination(sum_now + candidates[i], list_now + [candidates[i]])

    ans = set()
    try_combination(0, [])
    real_ans = []
    for item in ans:
        real_ans.append(list(item))
    return real_ans
\end{lstlisting}


\subsubsection{代码优化}
\begin{itemize}
    \item 【未优化版】代码里是通过python的set()来将结果去掉重复，分析一下回溯的过程，当尝试完第一个元素的所有可能的情况后，会尝试第二个元素的所有可能的情况，结果我们会发现，在尝试第二个元素的所有可能情况时，包含第一个元素的情况其实在尝试第一个元素的时候已经尝试过了。所以，在尝试第二个元素时，我们完全可以不去考虑第一个元素。
    \item 改变的地方就是递归调用时，不再每次都从0开始
\end{itemize}
\subsubsection{解题代码 - 优化1}
\begin{lstlisting}[language=python]
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    def try_combination_v2(start_index: int, sum_now: int, list_now: List[int]):
        nonlocal ans
        if sum_now == target:
            new_list = tuple(list_now)
            ans.add(new_list)
            return
        if sum_now > target:
            return

        for i in range(start_index, len(candidates)):
            try_combination_v2(i, sum_now + candidates[i], list_now + [candidates[i]])

    ans = set()
    try_combination_v2(0, 0, [])
    real_ans = []
    for item in ans:
        real_ans.append(list(item))
    return real_ans
\end{lstlisting}

\subsection{40. Combination Sum II}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 题目条件和39题一样，只是在组合$Target$时，$array$中每个索引对应的数字只能被使用一次。
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 难点如何实现每个索引对应的元素只使用一次，又因为不能有重复的组合
    \item 要去重首先要将$array$排序，这样重复的元素就会相邻
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    def dfs(begin, path, sum_now):
        nonlocal res, candidates_len
        # 判断是否满足条件
        if sum_now == target:
            res.append(path[:])
            return
        # 如果已经超过，就不进行后续的尝试
        if sum_now > target:
            return

        for i in range(begin, candidates_len):
            # 因为candidates已经是有序排列，如果已经超过target，就不再进行尝试了
            if sum_now + candidates[i] > target:
                break
            # 如果同样的位置上，之前已经尝试过了，就不再尝试
            if i > begin and candidates[i] == candidates[i - 1]:
                continue
            # 选择当前的元素
            path.append(candidates[i])
            # 进行下一个元素的尝试
            dfs(i + 1, path, sum_now + candidates[i])
            # 撤销之前的尝试
            path.pop()

    res = []
    candidates_len = len(candidates)
    if candidates_len == 0:
        return res

    candidates.sort()
    dfs(0, [], 0)
    return res
\end{lstlisting}

\subsection{41. First Missing Positive}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 给定一个无序的整数数组，找出其中没有出现的最小正整数
        \item 要求时间复杂度是$O(n)$，空间复杂度是$O(1)$
        \item 限定条件：最大数组长度是$5 * 10 ^ 5$，数据的大小是32位的整数范围
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 最小正整数是从1开始
    \item 时间复杂度是$O(n)$，也就是只能遍历一次数组
    \item 缺失的正整数的范围是$[1, 数组长度]$，在遍历时，如果数组里有1，就让1存放在数组的第一个元素，如果数组里有$n$，就让$n$保存在数组的第$n-1$个元素。在遍历完全部数组元素后，如果正整数$N$不在$nums[N-1]$就说明N缺失。
    这就是Leetcode里的置换法：在遍历数组的时候，即$nums[nums[i] - 1]$和$nums[i]$互换
    \begin{itemize}
        \item 这里要注意$nums[i] == nums[nums[i] - 1]$时，不去交换
        \item 如果$nums[i]$超过数组的长度，不去交换
        \item $nums[i]$是负数时，不去交换
    \end{itemize}
    \item 置换完所有的元素后，再次遍历数组，如果$nums[i] != i+1$，则i+1就是缺失的最小正整数
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def firstMissingPositive(self, nums: List[int]) -> int:
    nums_len = len(nums)

    for i in range(nums_len):
        while 0 < nums[i] <= nums_len and nums[i] != nums[nums[i] - 1]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    for i in range(nums_len):
        if nums[i] != i + 1:
            return i + 1

    return nums_len + 1
\end{lstlisting}

\subsection{42. Trapping Rain Water}
\begin{itemize}
    \item 难度：困难
	\item 题意分析：
    \begin{itemize}
        \item 给定一个包含非负整数的数组$heights$，每个元素代表柱子的高度，两根柱子之间可以接水，问按照数组元素排列的柱子能够接水的总量，这里假设柱子的宽度是1。
    \end{itemize}
\end{itemize}

\subsubsection{解题思路 - 动态规划}
\begin{itemize}
    \item 每根柱子能够接水的条件是柱子左右两边的柱子都比它高，接水的量由左右两边比它高的柱子中较低的柱子高度决定
    \item 如果针对每根柱子都遍历来求左右两边的最高柱子，每根柱子要遍历$n$根柱子，计算$n$根柱子，总的时间复杂度是$O(n^2)$
    \item 如果可以提前求得每根柱子的左右两边柱子的最大值，总的时间复杂度才有可能降低。这里可以用动态规划的方法来求。
    \begin{itemize}
        \item 如何求某根柱子左边柱子包含它自身高度的最大值，假设$left\_max[i]$表示第$i$根柱子以及它左边柱子的最大值，那么就有$left\_max[i] = max(left\_max[i-1], heights[i])$，这里$left\_max[0]=heights[0]$，这样从左遍历一次$heights$，就可以求出$left\_max$
        \item 如何求某根柱子右边柱子包含它自身高度的最大值，假设$right\_max[i]$表示第$i$根柱子以及它右边柱子的最大值，那么就有$right\_max[i] = max(right\_max[i+1], heights[i]$)，这里$right\_max[n-1] = heights[n-1]$，这样从右遍历一次$heights$，就可以求出$right\_max$
        \item 第$i$根柱子的接水量就是$min(left\_max[i], right\_max[i]) * heights[i]$
        \item 有3次遍历，每次的时间复杂度是$O(n)$，整个的时间复杂度是$O(n)$。有2个额外的数组，长度为n，所以空间复杂度是$O(n)$
    \end{itemize}
\end{itemize}

\subsubsection{解题代码 - 动态规划}
\begin{lstlisting}[language=python]
def trap(self, height: List[int]) -> int:
    ans = 0
    count = len(height)
    left_max = [0] * count
    right_max = [0] * count
    left_max[0] = height[0]
    right_max[count - 1] = height[count - 1]

    for i in range(1, count):
        left_max[i] = max(left_max[i - 1], height[i])

    for i in range(count - 2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])

    for i in range(count):
        ans += min(left_max[i], right_max[i]) - height[i]

    return ans
\end{lstlisting}

\subsubsection{解题思路 - 双指针法}
\begin{itemize}
    \item 每根柱子的接水量实际上是由$left\_max[i]$和$right\_max[i]$的最小值来决定的，那么有没有办法不需要求出全部的$left\_max$和$right\_max$，就可以计算呢？
    \item 从动态规划的运算过程可以看出，$left\_max$从左往右是递增的，$right\_max$从右往左是递增的
    \item 考虑从$height$左右两端开始遍历，保存左右两边的最大值，如果左边的最大值是较小的值，那么就可以计算左边柱子的接水量；如果右边的最大值是较小的值，那么就可以计算右边主子的接水量
    \item 因为还是需要遍历一遍$height$，所以整体的时间复杂度不变，还是$O(n)$。因为只需要固定数量的变量，所以时间复杂度为$O(1)$
\end{itemize}

\subsubsection{解题代码 - 双指针法}
\begin{lstlisting}[language=python]
def trap(self, height: List[int]) -> int:
    ans = 0
    left_index = 0
    right_index = len(height) - 1
    left_max = right_max = 0

    while left_index < right_index:
        left_max = max(left_max, height[left_index])
        right_max = max(right_max, height[right_index])

        if left_max < right_max:
            ans += left_max - height[left_index]
            left_index += 1
        else:
            ans += right_max - height[right_index]
            right_index -= 1

    return ans
\end{lstlisting}

\section{贪心算法}
% template - 题解
\subsection{55. Jump Game}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定一个正整数的数组$steps$，数组表示一串格子，每个元素的数值代表在该位置可以前进的最大格子数，问是否可以走到最后一个格子
    \end{itemize}
\end{itemize}

\subsubsection{解题思路 - 动态规划}
本题是可以用动态规划的方法来解决，但是会超时，下面是分析。
\begin{itemize}
    \item 设计一维数组$dp$，数组$dp[i]$表示是否可以到达第$i$个格子，True为可以达到，False为不能
    \item 因为是从第$0$个格子出发，所以$dp[0] = True$
    \item 递推公式
    \begin{itemize}
        \item 考虑$dp[i]$和$dp[j] (0 \leq j<i)$的元素的关系
        \item 对于任意第$j$格子，如果$dp[j]=True$，即能够到达第$j$个格子，如果同时满足$j+steps[j] \geq i$，那么就能到第$i$个格子；
        所以只需要遍历所有小于$i$的情况，只要有一个格子是满足到达条件的，那么就是能够到达第$i$个格子的
    \end{itemize}
    \item 时间复杂度分析
    \begin{itemize}
        \item 从代码可以看出，有两个for循环，每个都是$O(n)$，所以整体的时间复杂度是$O(n^2)$
        \item 题设的条件有$1 \leq steps.length \leq 3 \times 10^4 $，所以整体上运算会是$10^8$量级，很容易超时
    \end{itemize}
\end{itemize}
\subsubsection{解题代码 - 动态规划}
\begin{lstlisting}[language=python]
def canJump(self, nums: List[int]) -> bool:
    dp = [False] * len(nums)
    dp[0] = True

    for i in range(1, len(nums)):
        for j in range(0, i):
            if dp[j] and j + nums[j] >= i:
                dp[i] = True
                break

    return dp[-1]
\end{lstlisting}


\subsubsection{解题思路 - 贪心}
\begin{itemize}
    \item 贪心算法的核心思想是通过局部的最优解来构建全局的最优解
    \item 本题的问题是是否可以到达最后的格子，问题可以转换为能够最远达到的格子数$maxCell$，如果$maxCell$超过了最后的格子，那么就能够到达，反之就是到达不了
    \item 分析如何求每一步能够达到的最远距离，通过例子来说明，假设$steps=[2, 3, 1, 1, 4]$
    \begin{itemize}
        \item 第1步，最远能够达到第2个格子，$maxCell=2$
        \item 第2步，因为第一步覆盖了0，1，2三个格子，那么第2步所能够到达的最远格子应该是以格子1和2作为起点，
        所能够达到的最远的格子决定。那么就是第1个格子出发，迈出3步，到达第4个格子$maxCell=4$
    \end{itemize}
    \item 时间复杂度分析，从代码看，只有一个for循环，所以是$O(n)$
\end{itemize}

\subsubsection{解题代码 - 贪心}
\begin{lstlisting}[language=python]
def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    max_length = 0

    for i in range(n):
        if i <= max_length:
            max_length = max(max_length, i + nums[i])
            if max_length >= n - 1:
                return True

    return False
\end{lstlisting}

% template - 题解
\subsection{45. Jump Game II}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 题设条件与44题一样，只是要求解最小跳跃的次数
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 略
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def jump(self, nums: List[int]) -> int:
    n = len(nums)
    max_pos, end, step = 0, 0, 0

    for i in range(n - 1):
        if max_pos >= i:
            max_pos = max(max_pos, i + nums[i])
            if i == end:
                end = max_pos
                step += 1

    return step
\end{lstlisting}

\subsection{2136. Earliest Possible Day of Full Bloom}
\begin{itemize}
    \item 难度：困难
    \item 给出两个长度为$n$的数组$array1$和$array2$，$array1[i]$表示第$i$种花的种植时间，$array2[i]$表示第$i$种花的生长时间
    \item 种花规则如下
    \begin{itemize}
        \item 每次只能选择种一种花，在当前选择的花种植完毕后，才能开始种下一种花
        \item 只要花种植完毕后，花会自动生长，并且开花
    \end{itemize}
    \item 问题是给出两个数组，请计算出能够看到全部花开的最少的种花时间
\end{itemize}

\subsubsection{解题思路}
首先这是一道求最优解的题，本质是先后种花的顺序中，找出最优解，即整体花时间最少的解，从最后的解法看此题是贪心算法。

先分析一下只有两种花的情况：
\begin{itemize}
    \item 给定$array1=[p_1, p_2]$和$array2=[g_1, g_2]$
    \item 先种1再种2的顺序下，花全部开放的时间是 $max_{12}=\{p_1 + g_1, p_1 + p_2 + g_2\}$
    \item 先种2再种1的顺序下，花全部开放的时间是 $max_{21}=\{p_2 + g_2, p_2 + p_1 + g_1\}$
    \item 假设$g_1$ > $g_2$，则有如下的关系
    \begin{itemize}
        \item $p_2 + p_1 + g_1 > p_1 + p_2 + g_2 $
        \item $p_2 + p_1 + g_1 > p_1 + g_1 $
        \item $p_2 + p_1 + g_1 > max_{12}$
        \item $max_{21} > p_2+p_1+g_1 > max_{12}$
        \item $max_{21}$是按照生长时间升序来种花的全部开花时间，$max_{12}$是按照生长顺序降序来种花的全部开花时间
    \end{itemize}
    \item 得出的结果是，如果按照生长时间的升序顺序来种花得到的全部开花时间比按照生长时间降序顺序种花所得到全部开花时间长，所以应该按照生长时间降序的顺序来种花
\end{itemize}


\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
    array = list(zip(plantTime, growTime))
    # 按照growTime的降序排列
    array.sort(key=lambda x: -x[1])

    day, ans = 0, 0
    # flower[0]是种植时间,flower[1]是生长时间
    for flower in array:
        day += flower[0]
        # 对于第2个元素
        # ans = p0 + g0
        # day = p0 + p1
        # max = (p0 + g0, p0 + p1 + g1)
        ans = max(ans, day + flower[1])

    return ans
\end{lstlisting}

\subsection{2141. Maximum Running Time of N Computers}
\begin{itemize}
    \item 难度：困难
    \item 给一个整数$n$和一个正整数数组$batteries$，$n$代表电脑的台数，$batteries$表示一组电池,$batteries[i] = m$表示第$i$个电池可以给电脑供电$m$分钟
    \item 每台电脑同时只能由一个电池供电，电脑的电池可以在任意整数时刻进行切换，切换电池不花费时间，切换次数不限。
    \item 要求给出所有电脑同时工作的最长时间
\end{itemize}

\subsubsection{解题思路}


\subsubsection{解题代码}
\begin{lstlisting}{language=python}
def maxRunTime(self, n: int, batteries: List[int]) -> int:
    batteries.sort(reverse=True)
    s = sum(batteries)
    for b in batteries:
        if b <= s // n:
            return s // n
        s -= b
        n -= 1
\end{lstlisting}

% template - 刷题日志 - end

% template - 刷题日志 - begin
\section{滑动窗口}

% template - 题解
\subsection{438. Find All Anagrams in a String}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给定两个字符串$str1$和$str2$，要求在$str1$中寻找$str2$的异体词，返回异体词的起始坐标
        \item 异体词 - 由相同字母经过重新排列后形成的字符串（包含完全相同的字符串）
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 用长度为$len(str2)$的滑动窗口遍历$str1$
    \item 判断滑动窗口内的字符是否为$str2$的异体词
    \item 从异体词的定义可以看出，如果两个词的长度相同，并且包含的字母个数相同，则这两个字符串就是异体词，那么就可以通过统计字符串里包含的字母个数是否相等来判断是否为异体词
    \item 如果$str1$和$str2$的长度不同，直接返回空
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def findAnagrams(self, s: str, p: str) -> List[int]:
    s_len, p_len = len(s), len(p)

    if s_len < p_len:
        return []

    s_count = [0] * 26
    p_count = [0] * 26

    ans = []

    for i in range(0, p_len):
        s_count[ord(s[i]) - 97] += 1
        p_count[ord(p[i]) - 97] += 1

    if s_count == p_count:
        ans.append(0)

    for i in range(1, s_len - p_len + 1):
        s_count[ord(s[i-1]) - 97] -= 1
        s_count[ord(s[i+p_len-1]) - 97] += 1

        if s_count == p_count:
            ans.append(i)

    return ans
\end{lstlisting}
% template - 刷题日志 - end
% template - 题解
\subsection{2134. Minimum Swaps to Group All 1's Together II}
\begin{itemize}
    \item 难度：中等
	\item 题意分析：
    \begin{itemize}
        \item 给一个环形数组，里面包含$1$和$0$
        \item 可以进行的操作是每次交换一个位置的$1$和一个位置的$0$，经过诺干次这样的操作，就会让所有的$1$连在一起
        \item 给出最小的交换次数
    \end{itemize}
\end{itemize}

\subsubsection{解题思路}
\begin{itemize}
    \item 使用滑动窗口的思想，窗口长度为数组中$1$的个数，将这个窗口在环形数组中滑动，统计窗口中$0$的个数，最小值就是交换操作的最小次数
\end{itemize}

\subsubsection{解题代码}
\begin{lstlisting}[language=python]
def minSwaps(self, nums: List[int]) -> int:
    count_one = sum(nums)

    if count_one == 0 or count_one == 1:
        return 0

    one_in_window = 0
    ret_val = count_one
    nums_len = len(nums)

    # 计算初始的窗口（从nums[0]开始）内1的数量
    for i in range(count_one):
        one_in_window += nums[i]

    # 计算初始的移动次数
    ret_val = min(count_one, count_one - one_in_window)

    # 环形数组的长度是原数组长度加上滑动窗口的长度
    # i 表示要加入到滑动窗口的新元素
    for i in range(1, nums_len):
        # 计算移出的原属
        sub_value = nums[i - 1]

        # 计算追加的原属
        add_value = 0
        if i + count_one - 1 < nums_len:
            add_value = nums[i + count_one - 1]
        else:
            add_value = nums[i + count_one - 1 - nums_len]

        # 计算新的窗口里1的个数
        one_in_window = one_in_window + add_value - sub_value
        ret_val = min(ret_val, count_one - one_in_window)

        # 如果窗口里全是1，说明不用移动
        if ret_val == 0:
            break

    return ret_val
\end{lstlisting}



%-------------------------------------------------------
\chapter{参考}
\begin{itemize}
    \item Awesome cs book
    \begin{itemize}
        \item Github \href{https://hub.fastgit.org/imarvinle/awesome-cs-books}{https://hub.fastgit.org/imarvinle/awesome-cs-books}
        \item Gitee \href{https://gitee.com/Marvinle/awesome-cs-books}{https://gitee.com/Marvinle/awesome-cs-books}
    \end{itemize}
    \item 图 \href{https://zhuanlan.zhihu.com/p/25498681}{https://zhuanlan.zhihu.com/p/25498681}
    \item Github上的项目 \href{https://github.com/doocs/leetcode}{https://github.com/doocs/leetcode}
    \item 知乎上的算法合集 \href{https://zhuanlan.zhihu.com/p/105467597}{https://zhuanlan.zhihu.com/p/105467597}
\end{itemize}
% end of document
\end{document}